1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
const pii mod = {1e9 + 7, 1e9 + 9}, base = {131, 251};
const int N = 2e5 + 10;
pll operator + (const pll &a, const pll &b){
return {(a.first + b.first) % mod.first, (a.second + b.second) % mod.second};
}
pll operator - (const pll &a, const pll &b){
return {(a.first - b.first + mod.first) % mod.first, (a.second - b.second + mod.second) % mod.second};
}
pll operator * (const pll &a, const pll &b){
return {a.first * b.first % mod.first, a.second * b.second % mod.second};
}
pll hs[N], pw[N];
int n, f[N], m;
string a;
char s[N];
void init(){
hs[0] = {0, 0};
for(int i = 1; i <= n; i++){
pll ch = pll{a[i] - 'a' + 1, a[i] - 'a' + 1};
hs[i] = hs[i - 1] * base + ch;
}
for(int i = 1; i <= n; i++){
s[i << 1] = a[i];
s[i << 1 | 1] = '#';
f[i << 1] = f[i << 1 | 1] = 0;
}
f[0] = f[1] = 0;
int r, p, i;
s[0] = '$', s[1] = '#', s[m = (n + 1) << 1] = '@';
for(r = p = 0, f[1] = 1, i = 2; i < m; i += 1){
f[i] = r > i ? min(r - i, f[p * 2 - i]) : 1;
for(; s[i - f[i]] == s[i + f[i]]; f[i]++);
if(i + f[i] > r) r = i + f[i], p = i;
}
}
pll get(int l, int r){
return hs[r] - hs[l - 1] * pw[r - l + 1];
}
map<pll, int> mp;
struct node{
pll hash;
int cnt;
};
ll ans[N];
void solve(){
mp.clear();
cin >> a;
n = (int)a.size();
a = " " + a;
init();
for(int i = 1; i <= n; i++) ans[i] = 0;
set<int> st;
for(int i = 3; i + 2 < m; i += 2){
st.insert(i);
}
for(int i = 2; i < m; i += 2){
vector<int> del;
vector<node> res;
for(auto j : st){
int rt = j + f[j] - 1;
if(j > i) break;
if(i > rt){
del.push_back(j);
}else{
int l = (2 * j - i) / 2, r = i / 2;
pll hash_ = get(l, r);
if(mp.count(hash_)){
res.push_back({hash_, mp[hash_]});
ans[r] += mp[hash_];
break;
}
int ok = 0, mid = (l + r) >> 1;
if(get(l, mid) == get(mid + 1, r)) ok = 1;
ans[r] += ok;
res.push_back({hash_, ok});
}
}
for(int j : del){
st.erase(j);
}
reverse(res.begin(), res.end());
int pre = 0;
for(auto j : res){
pll ha = j.hash;
int cnt = j.cnt;
pre += cnt;
if(mp.count(ha)) continue;
mp[ha] = pre;
}
}
for(int i = 1; i <= n; i++){
ans[i] += ans[i - 1];
cout << ans[i] << " \n"[i == n];
}
}
int main(){
int T = 1;
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
pw[0] = {1, 1};
for(int i = 1; i <= N - 1; i++){
pw[i] = pw[i - 1] * base;
}
cin >> T;
while(T--) solve();
return 0;
}
|