【題目連結】
- BZOJ
- UOJ
【思路要點】
- 做兩次KMP,第一次求出Next數組,第二次保證比對位數不超過目前串的一半(否則視為失配),求出Num數組。
- 時間複雜度\(O(NL)\)。
【代碼】
#include<bits/stdc++.h> using namespace std; #define MAXN 1000005 #define P 1000000007 template <typename T> void read(T &x) { x = 0; int f = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') f = -f; for (; isdigit(c); c = getchar()) x = x * 10 + c - '0'; x *= f; } char s[MAXN]; int len[MAXN], num[MAXN], nxt[MAXN]; int main() { int T; read(T); while (T--) { scanf("\n%s", s + 1); int n = strlen(s + 1); nxt[1] = 0; num[1] = 1; for (int i = 2; i <= n; i++) { int j = nxt[i - 1]; 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; } long long ans = 1; int pos = 0; for (int i = 2; i <= n; i++) { while (pos && s[i] != s[pos + 1]) pos = nxt[pos]; if (s[i] == s[pos + 1]) pos++; if (pos > i / 2) pos = nxt[pos]; ans = ans * (num[pos] + 1) % P; } printf("%lld\n", ans); } return 0; }