洛谷题单指南-字符串-P2375 [NOI2014] 动物园

原题链接：https://www.luogu.com.cn/problem/P2375

题意解读：计算字符串所有子串的不重叠相同前后缀数量。

解题思路：

1、KMP+暴力

通过Next数组，可以计算所有子串相同前后缀的数量

然后枚举Next数组，通过回跳Next[j]、Next[Next[j]-1]、Next[Next[Next[j]-1] - 1]......来统计长度小于子串长度一半的前后缀个数，记录在num[]数组

50分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005, MOD = 1e9 + 7;
int n;
string s;
int Next[N], num[N];
long long ans = 1;

int main()
{
    cin >> n;
    while(n--)
    {
        memset(Next, 0, sizeof(Next));
        memset(num, 0, sizeof(num));
        cin >> s;
        ans = 1;
        //计算每个子串的最长相同前后缀长度,标准Next数组
        for(int i = 1, j = 0; i < s.size(); i++)
        {
            while(j && s[i] != s[j]) j = Next[j - 1];
            if(s[i] == s[j]) j++;
            Next[i] = j;
        }
        //统计每个子串前后缀不重叠的数量
        for(int i = 0; i < s.size(); i++)
        {
            int j = Next[i];
            while(j)
            {
                if(j * 2 <= i + 1) num[i]++;
                j = Next[j - 1];
            } 
        }
        //计算答案
        for(int i = 0; i < s.size(); i++)
        {
            ans = ans * (num[i] + 1) % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}

2、KMP+递推

由于枚举找到长度小于子串一半的前后缀复杂度整体是O(n^2)，需要进行优化

设Cnt[i]表示0~i子串的相同前后缀数量，根据定义可知cnt[i] = 0~Next[i]-1的相同前后缀数量 + 1，即Cnt[i] = Cnt[Next[i]-1] + 1

那么在计算Next的过程中，可以同时将Cnt[]通过递推计算出来。

for(int i = 1, j = 0; i < s.size(); i++)
{
    while(j && s[i] != s[j]) j = Next[j - 1];
    if(s[i] == s[j]) j++;
    Next[i] = j;
    if(j) Cnt[i] = Cnt[j - 1] + 1; //0~i的相同前后缀数量 = 0~Next[i]-1的相同前后缀数量 + 1
}

然后再进行一次Next计算过程，当找到一组前后缀匹配时，判断长度是否超过子串一半，一直往前跳到长度小于等于子串长度一半，此时Num[i]就是当前前后缀的长度j + Num[j-1]

for(int i = 1, j = 0; i < s.size(); i++)
{
    while(j && s[i] != s[j]) j = Next[j - 1];
    if(s[i] == s[j]) j++;
    while(j * 2 > i + 1) j = Next[j - 1]; //当前后缀长度超过子串一半时，不断缩减直到找到不超过子串一半的前后缀长度
    if(j) Num[i] = Cnt[j - 1] + 1; //0-i的不重叠相同前后缀数量 = 长度j的前后缀 + 0~j-1的相同前后缀数量
}

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005, MOD = 1e9 + 7;
int n;
string s;
int Next[N], Cnt[N], Num[N]; //Cnt[i]表示0~i子串中相同前后缀的数量
long long ans = 1;

int main()
{
    cin >> n;
    while(n--)
    {
        memset(Next, 0, sizeof(Next));
        memset(Cnt, 0, sizeof(Cnt));
        memset(Num, 0, sizeof(Num));
        cin >> s;
        ans = 1;
        //计算每个子串的最长相同前后缀长度,标准Next数组
        for(int i = 1, j = 0; i < s.size(); i++)
        {
            while(j && s[i] != s[j]) j = Next[j - 1];
            if(s[i] == s[j]) j++;
            Next[i] = j;
            if(j) Cnt[i] = Cnt[j - 1] + 1; //0~i的相同前后缀数量 = 0~Next[i]-1的相同前后缀数量 + 1
        }
        //统计每个子串前后缀不重叠的数量
        for(int i = 1, j = 0; i < s.size(); i++)
        {
            while(j && s[i] != s[j]) j = Next[j - 1];
            if(s[i] == s[j]) j++;
            while(j * 2 > i + 1) j = Next[j - 1]; //当前后缀长度超过子串一半时，不断缩减直到找到不超过子串一半的前后缀长度
            if(j) Num[i] = Cnt[j - 1] + 1; //0-i的不重叠相同前后缀数量 = 长度j的前后缀 + 0~j-1的相同前后缀数量
        }
        //计算答案
        for(int i = 0; i < s.size(); i++)
        {
            ans = ans * (Num[i] + 1) % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}