2023年ICPC亚洲合肥赛区赛 C. Cyclic Substrings

题目

题解

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
const int maxn = 6e6 + 5;
const int mod = 998244353;
int fail[maxn];//fail[i]表示i结点代表的回文串的最大回文后缀的编号 
int len[maxn]; //len[i]表示结点i代表的回文串的长度 
int trie[maxn][26], tot = 1;//tot初始为1！！！！ 
int cnt[maxn];//结点i代表的回文串出现了多少次
int ind[maxn];
string s;
int get(int x, int i){//x是以s[i-1]结尾的回文串，返回以s[i-1]结尾且s[i-len[x]-1]==s[i]的回文串的对应结点编号 while(i - len[x] - 1 < 0 || s[i - len[x] - 1] != s[i]) x = fail[x];return x;
}
signed main(){int i, j;int n;cin >> n;cin >> s;s = s + s;int cur = 0;int pos, last = 0;fail[0] = 1;fail[1] = 0;len[0] = 0;len[1] = -1;for(i = 0; i < 2 * n; i++){pos = get(cur, i);//cur是以s[i-1]结尾的最大回文串 int idx = s[i] - '0';if(!trie[pos][idx]){ tot++; int t = get(fail[pos], i);fail[tot] = trie[t][idx];ind[trie[t][idx]]++;trie[pos][idx] = tot;//把新建的结点接在pos下面 len[tot] = len[pos] + 2;// cnt[tot] = cnt[fail[tot]] + 1;}cur = trie[pos][idx];if(i > n - 1)//只计算以 后半串的字符 结尾的最长回文串，否则会重复cnt[cur]++;//结点cur代表的回文串出现了多少次}ll res = 0;queue<int> q;for(int i = 2; i <= tot; i++){// if(len[i] > n) continue;if(!ind[i]){q.push(i);}}while(!q.empty()){int u = q.front();q.pop();int v = fail[u];// if(len[v] > n) continue;cnt[v] += cnt[u];//一个回文串出现一次，那么它的回文后缀也出现一次if(--ind[v] == 0){q.push(v);}}for(int i = 2; i <= tot; i++){if(len[i] > n) continue;// cout << i << ' ' << len[i] << ' ' << cnt[i] << '\n';res = (res + 1LL * len[i] * cnt[i] % mod * cnt[i] % mod) % mod;}cout << res << '\n';return 0;
}