【kmp】next数组的应用 OKR-Periods of Words（最小公共前后缀）Radio Transmission(最大公共前后缀)

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

问题 L: 【KMP】Radio Transmission

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

题目描述

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

输入

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

输出

输出最短的长度。

样例输入

复制样例数据

8
cabcabca

样例输出

提示

我们可以利用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

样例输出

提示

对于全部数据，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 最小