参考博客: KMP 算法 (kuangbin)
另讲得比较好的博客或网站: 前缀函数与 KMP 算法 https://oi-wiki.org/string/kmp/ KMP 算法 (研究总结, 字符串) https://www.cnblogs.com/SYCstudio/p/7194315.html
- const int maxn=1e5;
- int Next[maxn];
- /* 求前缀数组 */
- /*t[0] 对应的 Next 数组值为 Next[1]*/
- /*Next[0]=-1 方便判断是否都不能匹配 */
- void getNext(string t)
- {
- int i=0,j=-1,n=t.length();
- Next[0]=-1;
- while(i<n)
- {
- if(j==-1||t[i]==t[j])
- Next[++i]=++j;
- else j=Next[j];
- }
- }
附输出中间变量:
- (有助于理解)
- void getNext(string t)
- {
- int i=0,j=-1,n=t.length();
- Next[0]=-1;
- while(i<n)
- {
- cout<<"i:"<<i<<"j:"<<j<<endl;
- if(j==-1||t[i]==t[j])
- Next[++i]=++j,cout<<"Next:"<<i<<"j:"<<j<<endl;
- else j=Next[j];
- }
- }
- t:ababbbaaaba
- i:0 j:-1
- Next:1 j:0
- i:1 j:0
- i:1 j:-1
- Next:2 j:0
- i:2 j:0
- Next:3 j:1
- i:3 j:1
- Next:4 j:2
- i:4 j:2
- i:4 j:0
- i:4 j:-1
- Next:5 j:0
- i:5 j:0
- i:5 j:-1
- Next:6 j:0
- i:6 j:0
- Next:7 j:1
- i:7 j:1
- i:7 j:0
- Next:8 j:1
- i:8 j:1
- i:8 j:0
- Next:9 j:1
- i:9 j:1
- Next:10 j:2
- i:10 j:2
- Next:11 j:3
前缀数组
来源: http://www.bubuko.com/infodetail-3148983.html