Description：

对于一个字符串的每个前缀求出既是他的后缀也是他的前缀且长度不超过他的一半的字符串个数。

$1\le n \le 1000000$

Solution：

首先肯定要跑一个 $KMP$ ，记 $ans[]$ 表示没有长度限制的个数，然后一种暴力的做法是每次暴力跳 $nxt[]$ 直到长度小于 $\lfloor\frac i 2\rfloor$ ，然而这样会被全部相同的卡成 $O(n^2)$ ，由于每靠后一位， $\lfloor\frac i 2\rfloor$ 也最多跳一位，所以类似 $KMP$ 的用一个 $j$ 表示不超过 $\lfloor\frac i 2\rfloor$ 的既是前缀也是后缀的长度，每次把 $j$ 按照字符串匹配那样先跳 $nxt[]$ 再后移一位，再用这一位的 $ans$ 更新答案。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

#define MOD 1000000007

int n;

#define MAXL 1000010

typedef long long ll;

char s[MAXL];

int nxt[MAXL];

int ans[MAXL];

int main()

{

	scanf("%d",&n);

	for(int t = 1;t <= n;++t)

	{

		scanf("%s",s + 1);

		int l = strlen(s + 1);

		ans[1] = 1;nxt[1] = 0;

		for(int i = 2,j = 0;i <= l;++i)

		{

			while(j && s[i] != s[j + 1])j = nxt[j];

			if(s[i] == s[j + 1])++j;

			nxt[i] = j;

			ans[i] = ans[j] + 1;

		}

		ll res = 1;

		for(int i = 1,j = 0;i <= l;++i)

		{

			while(j && s[j + 1] != s[i])j = nxt[j];

			if(s[j + 1] == s[i])++j;

			while(j > i / 2)j = nxt[j];

			res = res * (ans[j] + 1) % MOD;

		}

		cout << res << endl;

	}

	return 0;

}