KMP算法在字符串中的应用

链接&＃xff1a;https://icpcarchive.ecs.baylor.edu/index.php?option&＃61;com_onlinejudge&Itemid&＃61;8&page&＃61;show_problem&problem&＃61;1027

题解&＃xff1a;

根据后缀函数的定义&＃xff0c;“错位部分”长度为i-f[i]&＃xff0c;如果这i个字符组成一个周期串&＃xff0c;那么“错位”部分恰好是一个循环节&＃xff0c;因此k(i-f[i])&＃61;i&＃xff08;注意k>1&＃xff0c;因此i-f[i]不能等于i&＃xff0c;必须有饭f[i]>0)

#include
#include
#include
#include
using namespace std;
const int maxn&＃61;1000000&＃43;10;
int f[maxn];
string p;
int main()
{int n,cas&＃61;0;while(cin>>n){if(n&＃61;&＃61;0) break;cin>>p;f[0]&＃61;0;f[1]&＃61;0;for(int i&＃61;1;i0&&i%(i-f[i])&＃61;&＃61;0)printf("%d %d\n",i,i/(i-f[i]));cout<}


KMP裸题&＃xff08;求子串重复的次数&＃xff09; &＃xff08;本人poj的第50题&＃xff09;

链接&＃xff1a; http://poj.org/problem?id&＃61;3461

#include
#include
#include
using namespace std;
const int maxn&＃61;1000000&＃43;10;
int f[maxn];
char p[maxn],t[maxn];
int main()
{int k;cin>>k;while(k--){cin>>p>>t;int n&＃61;strlen(t),m&＃61;strlen(p);memset(f,0,sizeof(f));f[0]&＃61;0;f[1]&＃61;0;for(int i&＃61;1;i}


KMP找出第一次出现匹配的位置&＃xff1a;

链接&＃xff1a;http://acm.hdu.edu.cn/showproblem.php?pid&＃61;1711

#include
#include
#include
using namespace std;
const int maxn&＃61;1000000&＃43;10;
int p[maxn],t[maxn];
int f[maxn];
int main()
{int k;scanf("%d",&k);while(k--){int n,m;scanf("%d%d",&n,&m);for(int i&＃61;0;i}


求最短的重复串出现的次数

链接&＃xff1a;http://poj.org/problem?id&＃61;2406

思路&＃xff1a;KMP&＃xff0c;next表示模式串如果第i位(设str[0]为第0位)与文本串第j位不匹配则要回到第next[i]位继续与文本串第j位匹配。则模式串第1位到next[n]与模式串第n-next[n]位到n位是匹配的。所以思路和上面一样&＃xff0c;如果n%&＃xff08;n-next[n]&＃xff09;&＃61;&＃61;0,则存在重复连续子串&＃xff0c;长度为n-next[n]。

例如&＃xff1a;a    b    a    b    a    b

next:-1   0    0    1    2    3    4

next[n]&＃61;&＃61;4,代表着&＃xff0c;前缀abab与后缀abab相等的最长长度&＃xff0c;这说明&＃xff0c;ab这两个字母为一个循环节&＃xff0c;长度&＃61;n-next[n];

#include
#include
#include
using namespace std;
const int maxn&＃61;1000000&＃43;10;
char p[maxn];
int f[maxn];
int main()
{while(scanf("%s",p)!&＃61;EOF){if(p[0]&＃61;&＃61;&＃39;.&＃39;) break;int n&＃61;strlen(p);memset(f,0,sizeof(f));f[0]&＃61;0;f[1]&＃61;0;for(int i&＃61;1;i}