题目地址:http://acm.hdu.edu.cn/showproblem.php?pid=3336

题目:


求给定字符串每个前缀在整个字符串出现的次数之和

 

解题思路:


初始答案为n,每个前缀都出现一次。

字符串的下标从0开始存,next[0]=-1,当next[i]≠0且≠-1时,说明子串的某个前缀(也是整个字符串的前缀)和整个子串的某个后缀相同,即整个字符串的前缀重复出现了一次,对答案贡献1,遍历next数组统计答案即可。

 

ac代码:


#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
const int mod = 10007;
typedef long long ll;
int nxt[maxn];
char s[maxn];
int n;
void get_nxt()
{
    int i = 0, k = -1;
    nxt[0] = -1;
    while(i < n)
    {
        if(k == -1 || s[i] == s[k])
        {
            i++;
            k++;
            nxt[i] = k;
        }
        else k = nxt[k];
    }
}
int main() {
   // freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d", &n);
        scanf("%s", s);
        get_nxt();
        ll ans = n % mod;
        for(int i = 0; i <= n; i++)
            if(nxt[i] != -1 && nxt[i] != 0) ans = (ans + 1) % mod;
        printf("%lld\n", ans);
    }
    return 0;
}