看了好久的kmp终于懂了，做几个题目热热身

问题 L: 【KMP】Radio Transmission

时间限制: 1 Sec  内存限制: 128 MB
提交: 69  解决: 27
[提交] [状态] [命题人:admin]

 

题目描述

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

 

输入

第一行给出字符串的长度L，第二行给出一个字符串，全由小写字母组成。

 

输出

输出最短的长度。

 

样例输入

复制样例数据

8
cabcabca

样例输出

3

 

提示

我们可以利用abc不断自我连接得到abcabcabc，读入的cabcabca是它的子串。

对于全部数据，1≤L≤106

题解思路：考虑next数组的性质 ，分以下三种情况：

abab  next[n]=2 因为 由两个ab组成

ababa next[n]=3 因为由两个 aba组成

abababa next[n]=5  因为由两个ababa组成

所以说 这个字符串如果最后的循环节没有完成 :比如ababa 他就会使本来的 ab前后缀 加一变成aba前后缀，所以我们这样考虑：每在最小循环节上复制一次 他的最长公共前后缀就会增加他复制的长度，把最小循环节空出来，所以我们可以得到，最小正周期

T=n-next[n]；

AC：

//#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[maxn];
int f[maxn];
void restart()
{
    f[0]=-1;
    int i=-1,j=0;
    while(j<n)
    {
        if(i==-1||s[j]==s[i])
        {
            i++;
            j++;
            f[j]=i;
        }
        else
            i=f[i];
    }
}
int main()
{
    scanf("%lld%s",&n,s);
    restart();
    bool fl=false;
    printf("%lld\n",n-f[n]);
    return 0;
}

总结：根据这个题我们还能缩小我们之前求最小正周期的算法(二层循环)，直接预处理next数组，n-f[n]即为最小正周期

问题 M: 【KMP】OKR-Periods of Words

时间限制: 1 Sec  内存限制: 128 MB
提交: 40  解决: 16
[提交] [状态] [命题人:admin]

 

题目描述

串是有限个小写字符的序列，特别的，一个空序列也可以是一个串。一个串P是串A的前缀，当且仅当存在串B，使得A=PB。如果P≠A并且P不是一个空串，那么我们说P是A的一个proper前缀。
定义Q是A的周期，当且仅当Q是A的一个proper前缀并且A是QQ的前缀（不一定要是proper前缀）。比如串abab和ababab都是串abababa的周期。串A的最大周期就是它最长的一个周期或者是一个空串（当A没有周期的时候），比如说，ababab的最大周期是abab。串abc的最大周期是空串。
给出一个串，求出它所有前缀的最大周期长度之和。

 

输入

第一行一个整数k，表示串的长度。
接下来一行表示给出的串。

 

输出

输出一个整数表示它所有前缀的最大周期长度之和。

 

样例输入

复制样例数据

8
babababa

样例输出

24

 

提示

对于全部数据，1<k<106

题解：上个题我们求的最小正周期，这个题让我们求最大正周期，我们知道next数组求的是最大公共前后缀，所以n-f[n]绝对是最小正周期，那最大正周期呐？我们运用next数组的性质，不断判断这个位置i的最小公共前后缀是多少 只要next[next[i]]>0 说明 next[i]=next[next[i]]（只要！=0||！=-1说明还有最大公共前后缀我们不停的缩小），最后i-next[i]结果，过程中next[i]可以快速更新：

AC:

//#include <bits/stdc++.h>
#include<stdio.h>
#include <string.h>
#include<algorithm>
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=998244353;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
char s[maxn];
int f[maxn];
void restart()
{
    f[0]=-1;
    int i=-1,j=0;
    while(j<n)
    {
        if(i==-1||s[j]==s[i])
        {
            i++;
            j++;
            f[j]=i;
        }
        else
            i=f[i];
    }
   /* for(int i=0;i<=n;i++)
        printf("%d ",f[i]);*/
}
int main()
{
    scanf("%lld%s",&n,s);
    restart();
    bool fl=false;
    ll ans=0;
    for(int i=1;i<=n;i++)
    {
        while(f[f[i]]>0) f[i]=f[f[i]];
        printf("%d ",f[i]);
        if(f[i]!=0) ans+=i-f[i];
    }
    printf("%lld\n",ans);
    return 0;
}

总结：掌握了求最小公共前后缀的办法，原理用例子解释一下：ababa next[5]=3 next[3]=1 next[1]=0 所以next[5]=1 最小