字符串模板

dream_qwq · 2022-11-21 13:02:37 · 算法·理论

这是一篇关于*字符串模板*的文章这些是其他模板分类的链接	数据结构	数学	杂项	图论

前缀函数与 KMP 算法

P3375 【模板】KMP字符串匹配
```
int p[N]={-1};
```

void kmp(string s1, string s2){ int i=1, j=0, n1=s1.size(), n2=s2.size(); while(i<n2 && j<n2){ if(j==-1 || s2[i]==s2[j]) p[++i]=++j; else j=p[j]; }

i=0, j=0;
while(i<n1 && j<n2){
    if(j==-1 || s1[i]==s2[j]) i++, j++;
    else j=p[j];
    if(j==n2){
        printf("%d\n",i-n2+1);
        j=p[j];
    }
}

}