TLE 提交记录

#include<iostream>
#include<cstring>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int len, nxt[N], num[N];
char s[N];

void slove()
{
	memset(nxt, 0, sizeof(nxt));
	memset(num, 0, sizeof(num));
	ll ans = 1;
	cin >> s + 1;
	len = strlen(s + 1);
	nxt[1] = 0;
	num[1] = 1;
	for(int i = 2, j = 0; i <= len; i ++ )
	{
		while(j && s[i] != s[j + 1]) j = nxt[j];
		if(s[i] == s[j + 1]) j ++;
		nxt[i] = j;
		num[i] = num[j] + 1;
		int jj = j;
		while(jj > i / 2) jj = nxt[jj];
		ans = (ans * (num[jj] + 1)) % mod;
	}
	cout << ans << endl;
}

int main()
{
	int T;
	cin >> T;
	while(T -- ) slove();
	return 0;
}

AC 提交记录

#include<iostream>
#include<cstring>

using namespace std;

typedef long long ll;

const int N = 1e6 + 5;
const int mod = 1e9 + 7;

int len, nxt[N], num[N];
char s[N];

void slove()
{
	memset(nxt, 0, sizeof(nxt));
	memset(num, 0, sizeof(num));
	ll ans = 1;
	cin >> s + 1;
	len = strlen(s + 1);
	nxt[1] = 0;
	num[1] = 1;
	for(int i = 2, j = 0; i <= len; i ++ )
	{
		while(j && s[i] != s[j + 1]) j = nxt[j];
		if(s[i] == s[j + 1]) j ++;
		nxt[i] = j;
		num[i] = num[j] + 1;
	}
	for(int i = 1, j = 0; i <= len; i ++ )
	{
		while(j && s[i] != s[j + 1]) j = nxt[j];
		if(s[i] == s[j + 1]) j ++;
		while(j > i / 2) j = nxt[j];
		ans = (ans * (num[j] + 1)) % mod;
	}
	cout << ans << endl;
}

int main()
{
	int T;
	cin >> T;
	while(T -- ) slove();
	return 0;
}