本文共 1152 字，大约阅读时间需要 3 分钟。

首先设置一个数组用来举例子。

第一种方法

利用原理角度，也就是书本上给我们所讲的角度去解决，我们知道，所谓的next数组描绘的是数组的字符串对称程度。简单来说，字符串的对称程度越高，next数组就越大，但是这里的对称程度也不是类似于abccba这种，而是abcabc这种。我们默认为第一第二个next数组值为0,1即：

从第三位开始的next数组值：若该位前一位对应的next值那一位等于该位数据，则该位的next数值等于前一位加1.若不等：		则顺着next值往前找，直到某个值对应next的对应的值，与需要的值相等。		则next值等于那上面那个某个值的next加一，若没找到则为1.

ok,我们来看。

对第三位来说，2对应1，a!=b则，第三位的next为1.

对第四位来说，a对应1，a=a，则对1+1,4位的next值为2 对第五位来说，b对应2,b=b，则2+1=3，5位的next值为3 对第六位来说，a对应3,a=a，则第六位的next值为3+1=4 对第七位来说，a对应4，a!=b，往前找，到2，a!=b,则改变思路，往前找，显然b的next值位置为a则a=a，则为1+1=2，则第七位next值为2 对第八位来说，a对应2，a!=b，则改变思路，往前找，显然b的next 1对应的a=a，则1+1=2 对第九位来说，b对应2，显然相等，2+1=3.

可自己尝试填充剩下的，完整如下： 这里可能部分小伙伴会在第六处和第七处开始有点蒙，我在细说一下，第六处刚开始的a对应4，我们到4的位置查找，显然a!=b，那么就换思路判断，我们找4对应的值的next显然，4对应的next为2,2对应next为1，而这个1位置的是a，也就是等于第六位的a，则，我们对这个1加1获得2.

第二种方法

取前后缀子串，找相同的串数，用最大相等长度+1.

同样的例子：

求第三位，我们看，ab，前缀串有a，后缀串有b，相同的串数为0，则最大相等长度为0，则0+1=1获得1。

求第四位，我们看aba,前缀有a,ab后缀有a,ba,最大相等的长度为1，则1+1=2，获得2. 求第五位，看abab,前缀有a,ab,aba后缀有b,ab,bab,显然相等最长串为ab,长度为2，则2+1=3，获得3 求第六位，看ababa,前缀有a,ab,aba,abab后缀有a,ba,aba,baba最长相等串为aba，长度为3，则3+1=4获得4. 求第七位，看ababaa,前缀有a,ab,aba,abab,ababa后缀a,baa,abaa,babaa,显然最长相等为a，1+1=2.获得2 求第八位，看ababaaa,还是看前缀，看后缀，最长相等串为a，长度为1，则1+1=2，获取2 后面同理求出，所需要的完整为：

转载地址：http://zkcki.baihongyu.com/