其实这个问题就是kmp的子串的预处理
以往的做法里我们是这样做的:
法一:
for(int i=2;i<=lenb;i++){
while(j && b[j+1] != b[i]) j = nxt[j];
if(b[j+1] == b[i]) j++;
nxt[i] = j;
}
定义 next [ i ] 为 prefix[ i ] 的最大border
一个字符串的次大border一定是最大border的border
通过势能分析 得出算法时间复杂度为 O(N)
求解next[i]数组:
next[i] = preffix[i] 的非平凡的最大border
next[1] = 0;
考虑prefix[i] 的所有长度大于1的border 去掉最后一个字母 就会变成prefix[i-1]的border
因此我们求next[i]的时候 可以遍历prefix[i-1]的所有border 即next[i-1],next[next[i-1]] --- 0
检查最后一个字符是否等于s[i]:
法二:
for(int i=2;i<=lenb;i++){
nxt[i] = nxt[i-1];
while(nxt[i]&&b[i]!=b[nxt[i] + 1]) nxt[i] = nxt[nxt[i]];
nxt[i] += (b[i] == b[nxt[i] + 1]);
}