KMP题目网址：https://vjudge.net/contest/330283#overview

挑了一些典型的题目写一下

HDU - 1686： https://vjudge.net/contest/330283#problem/B

题意：

给出俩个字符串a和b，问你字符串a在字符串b的总出现次数是多少，即aaa在aaaa中出现了2次

题解：

kmp算法，在函数中当j==l2的时候令j=next[j]

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxx = 10005;
int next1[maxx],cnt = 0;
char s1[maxx*100],s2[maxx];
void getnext(char s[]){
    int j=0,k=-1,len = strlen(s);
    next1[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            next1[++j] = ++k;
        }
        else
            k = next1[k];
    }
}
int kmp(char s1[],char s2[])
{
    getnext(s2);
    int i=0,j=0;
    int l1 = strlen(s1),l2 = strlen(s2);
    while(i < l1){
        if(j == -1 || s1[i] == s2[j])
            i++,j++;
        else
            j = next1[j];
        if(j == l2){
            cnt++;
            j = next1[j];
        }
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cnt = 0;
        scanf("%s",s2);
        scanf("%s",s1);
        kmp(s1,s2);
        printf("%d\n",cnt);
    }
    return 0;
}

HDU - 2087：https://vjudge.net/contest/330283#problem/C

题意：

和上一题题意差不多，但是是求不重复覆盖的子字符串的出现次数，比如aa在aaaaaa中出现了3次

题解：

在kmp函数中，当j==l2的时候j=0即可

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxx = 1005;
int next1[maxx],cnt = 0;
char s1[maxx],s2[maxx];
void getnext(char s[]){
    int j=0,k=-1,len = strlen(s);
    next1[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            next1[++j] = ++k;
        }
        else
            k = next1[k];
    }
}
void kmp(char s1[],char s2[])
{
    getnext(s2);
    int i=0,j=0;
    int l1 = strlen(s1),l2 = strlen(s2);
    while(i < l1){
        if(j == -1 || s1[i] == s2[j])
            i++,j++;
        else
            j = next1[j];
        if(j == l2){
            cnt++;
            j = 0;
        }
    }
}
int main()
{
    while(~scanf("%s %s",s1,s2))
    {
        cnt = 0;
        if(strcmp(s1,"#") == 0){
            break;
        }
        kmp(s1,s2);
        printf("%d\n",cnt);
    }
    return 0;
}

HDU - 3746：https://vjudge.net/contest/330283#problem/D

题意：

给出一个字符串，要求将其补全成一个可以循环的字符串，输出最少添加的字符的个数，如果本身就是一个循环的字符串，输出0

题解：

用kmp求出来next数组，那么len - next[len] 就代表循环字符串的长度

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxx = 100005;
int next1[maxx],cnt = 0;
char s1[maxx];
void getnext(char s[]){
    int j=0,k=-1,len = strlen(s);
    next1[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            next1[++j] = ++k;
        }
        else
            k = next1[k];
    }
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s",s1);
        getnext(s1);
        int len = strlen(s1);
        if(!next1[len]){
            printf("%d\n",len);
            continue ;
        }
        int k = len - next1[len];
        if(len % k == 0)
            printf("0\n");
        else
            printf("%d\n",k-len%k);
    }
    return 0;
}

POJ - 2406：https://vjudge.net/contest/330283#problem/F

题意：

给出一个字符串，输出这个字符串最多可以分成几个相同的子字符串，例如ababab可以拆成3个ab，输出3

题解：

kmp求next数组，那么i - next[len]是循环字符串的长度，如果len%(i-next[len]) == 0，说明可以拆成至少2个子字符串，输出len/(i-next[len])；否则输出1.

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxx = 1000005;
int next1[maxx],cnt = 0;
char s1[maxx];
void getnext(char s[]){
    int j=0,k=-1,len = strlen(s);
    next1[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            next1[++j] = ++k;
        }
        else
            k = next1[k];
    }
}
int main()
{
    while(~scanf("%s",s1))
    {
        if(strcmp(s1,".") == 0)
            break;
        int len = strlen(s1);
        getnext(s1);
        int k = len - next1[len];//循环节的长度！！！
        if(len%k == 0){
            printf("%d\n",len/k);
            continue ;
        }
        printf("1\n");
    }
    return 0;
}

POJ - 1961：https://vjudge.net/contest/330283#problem/E

题意：

这算是和上一题的问题差不多，只不过多了个循环

题解：

循环求i-next[i]

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxx = 1000005;
int next1[maxx],cnt = 0;
char s1[maxx];
void getnext(char s[]){
    int j=0,k=-1,len = strlen(s);
    next1[0] = -1;
    while(j < len){
        if(k == -1 || s[j] == s[k]){
            next1[++j] = ++k;
        }
        else
            k = next1[k];
    }
}
int main()
{
    int len,t = 0;
    while(~scanf("%d",&len))
    {
        if(len == 0)
            break;
        scanf("%s",s1);
        getnext(s1);
        printf("Test case #%d\n",++t);

        for(int i=2;i<=len;i++)
        {
            int len2 = i - next1[i];//存在的循环节的长度！！！
            if(i%len2 == 0 && i != len2){
                printf("%d %d\n",i,i/len2);
            }
        }
        printf("\n");
    }
    return 0;
}

POJ - 2752：https://vjudge.net/contest/330283#problem/G

题意：

这算是这一套最好的一道题，彻底弄明白next数组，输入一个字符串，输出字符串的前缀，后缀长度相同且字符完全匹配的长度

题解：

递归，先kmp求出next数组，从next[len]往前递归，

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
using namespace std;
const int maxx = 400005;
int next1[maxx],ans[maxx],cnt = 0;
char s1[maxx];
void getnext(char s[]){
    int i=0,j=-1,len = strlen(s);
    next1[0] = -1;
    while(i < len){
        if(j == -1 || s[i] == s[j]){
            next1[++i] = ++j;
        }
        else
            j = next1[j];
    }
}
int main()
{
    while(~scanf("%s",s1))
    {
        int sum = 0;
        int len = strlen(s1);
        getnext(s1);
        int k = next1[len];
        while(k > 0){
            ans[++sum] = k;
            k = next1[k];
        }
        for(int i=sum;i>=1;i--){
            printf("%d ",ans[i]);
        }
        printf("%d\n",len);
    }
    return 0;
}