KMP深入理解——next数组求最大周期，最小循环节

next数组求最大周期
P3435 [POI2006] OKR-Periods of Words

题意：
给定一个字符串，请你求出这个字符串的所有前缀的最大周期和。

周期：一个串s的前缀a重复两次能够令s成为aa的子串称a为s的周期。

思路：我们利用kmp的next数组来求解，

next数组的含义：next[i]代表字符串的第i个前缀a的既是其前缀又是其后缀的串的长度。

next的用意：我们通过next数组能够避免从头开始寻找目前串的匹配，可以直接寻找目前满足这个子串最长既是其前缀又是其后缀的串。

对于这个题，我们通过next数组可以直接不断递推出当前串的循环节。

我们对于第i个前缀，先令j=i，不断的令j=nex[j],直到当前的nex[j]指示为空集，然后就能得到当前前缀的最小循环节为i-j。

对于这个循环节来讲，整个第i个前缀都是其appear length

#include
#include
#include
#include
using namespace std;
const int N = 1e6+100;
int n,len2;
int nex[N];
char s2[N];
inline void get_nex() //求出nex数组
{ //nex数组是从 S[0到i-1]前子串 的前缀后缀最大值
    int t1=0,t2;
    nex[0]=t2=-1;
    while(t1<len2)
        if(t2==-1 || s2[t1]==s2[t2]) //类似于KMP的匹配
            nex[++t1]=++t2;
        else t2=nex[t2];//失配
}

int main()
{
    cin>>len2;
    scanf("%s",s2);
    get_nex();
    long long ans=0ll;
    for(int i=1;i<=len2;i++)
    {
        int j=i;
        while(nex[j])
            j=nex[j];
        if(nex[i])
            nex[i]=j;//记忆化
        ans+=i-j;
    }
    cout<<ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

J. MUV LUV EXTRA

题意：给定一个字符串和两个常数a，b。请你求出其后缀的所有最小循环节长度l，并且计算ap-bl的最小值

思路：暴力求解必然会超时。我们想一下怎么利用kmp的next数组求解

next数组的含义上一题也说过了。

最小循环节能看出来就是：s的长度减去s的最长的既是前缀又是后缀的子串的长度。

比如：ababa 他的最长公共前后缀长度为3是aba，那么他的最小循环节应该就是ab，可以视为把s末尾的aba去掉了。因为aba是公共前后缀，所以去掉后一样可以通过ab重复多次来获得。

注意：题目的式子可能有负数，所以初始答案值设为无穷小。

#include
#include
#include
#include
using namespace std;
#define int long long
const int N = 1e7+100;
int n,nex[N],a,b;
char s[N];
void get_next()
{
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&s[i]!=s[j+1])
            j=nex[j];
        if(s[j+1]==s[i])
            j++;
        nex[i]=j;
    }
}
signed main()
{
    cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
    cin>>a>>b;
    string t;
    cin>>t;
    for(int i=t.length()-1;i>=0;i--)
    {
        if(t[i]=='.')
            break;
        s[++n]=t[i];
    }
    get_next();
    int ans=-1e18;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,a*i-b*(i-nex[i]));
    }
    cout<<ans;
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42