HDU-3336-Count the string（KMP-Next数组性质）

博主链接

题目链接

题意：

求一个串中所有前缀子串出现次数之和

题解：

对于每个串他前缀串出现次数和一定大于或等于n,因为有n个前缀；所以此时只需要去计算一下每一个前缀在后面出现了几次，也就是next数组的值。结合next数组的性质可以很容易得知，next数组中存在一个非0位，就出现了一种前缀，ans就++。所以只需对字符串求一遍next数组，统计都是个非零元素就可以了。

代码：

#include<stdio.h>
#include<bits/stdc++.h>
#define met(a) memset(a,0,sizeof(a))
#define fup(i,a,n,b) for(int i=a;i<n;i+=b)
#define fow(j,a,n,b) for(int j=a;j>0;j-=b)
#define MOD(x) (x)%mod
using namespace std;
const int maxn = 2*1e6 + 10;
const int mod = 1e9 + 7;
typedef long long ll;
char s[maxn];
int nex[maxn];
void Get_nex() {
	int j = 0;
	for (int i = 1; s[i]; i++) {
		while (s[i] != s[j + 1] && j != 0)j = nex[j];
		if (s[i] == s[j + 1] && i != 1)j++;
		nex[i] = j;
	}
}
int main() {
	int t,n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		scanf("%s", s+1);
		int ans = 0;
		Get_nex();
		for (int i = 1; i <=n; i++) {
			if (nex[i] != 0)ans++;
		}
		printf("%d\n", (n + ans) % 10007);
	}
}