C++(g++ 7.5.0) 解法, 执行用时: 576ms, 内存消耗: 577620K, 提交时间: 2023-02-04 15:29:00

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x)
{
	x=0;short f=1;char c=getchar();
	for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	x*=f;return;
}
const int N=5e6+5;
const int mod=998244353;
void qadd(int &x, int y){(x+=y)>=mod?(x-=mod):0;}
int n,ans,two[N];
char s[N],t[N];
int ch[N][26],len[N],fail[N],L,tot,lst;
void init()
{
	tot=1;
	len[0]=0;len[1]=-1;
	fail[0]=1;fail[1]=0;
	lst=0;
}
int getfail(int x)
{
	while(s[L-len[x]-1]!=s[L])x=fail[x];
	return x;
}
void insert(char c)
{
	s[++L]=c;
	int now=getfail(lst);
	if(!ch[now][c-'a'])
	{
		int x=++tot;len[x]=len[now]+2;
		fail[x]=ch[getfail(fail[now])][c-'a'];
		if(len[fail[x]]&&len[x]%(len[x]-len[fail[x]])==0)
			qadd(ans,two[len[x]/(len[x]-len[fail[x]])-1]);
		else qadd(ans,1);
		ch[now][c-'a']=x;
	}
	lst=ch[now][c-'a'];
}
int main()
{
	scanf("%s",t+1);
	n=strlen(t+1);
	two[0]=1;
	for(int i=1;i<=n;i++) two[i]=2ll*two[i-1]%mod;
	init();
	for(int i=1;i<=n;i++) insert(t[i]);
	printf("%d\n",ans);
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 668ms, 内存消耗: 577700K, 提交时间: 2023-02-03 21:27:51

#include <bits/stdc++.h>
#define N 5000005
using namespace std;

const int mod = 998244353;
inline void qadd(int &x, int y) { (x+=y)>=mod?(x-=mod):0; }

int n, ans, two[N];
char s[N], t[N]; 

int ch[N][26], len[N], fail[N], L, tot, lst;
void init() {
	tot = 1;
	len[0] = 0; len[1] = -1;
	fail[0] = 1; fail[1] = 0;
	lst = 0;
}
int getfail(int x) {
	while (s[L-len[x]-1] != s[L]) x = fail[x];
	return x;
}

void insert(char c) {
	s[++L] = c;
	int now = getfail(lst);
	if (!ch[now][c-'a']) {
		int x = ++tot; len[x] = len[now]+2;
		fail[x] = ch[getfail(fail[now])][c-'a'];
		if (len[fail[x]] && len[x]%(len[x]-len[fail[x]]) == 0) {
			qadd(ans, two[len[x]/(len[x]-len[fail[x]])-1]);
		} else qadd(ans, 1);
		ch[now][c-'a'] = x;
	}
	lst = ch[now][c-'a'];
}

int main() {
	scanf("%s", t+1); n = strlen(t+1);
	two[0] = 1;
	for (int i = 1; i <= n; i++) two[i] = 2ll*two[i-1]%mod;
	init(); 
	for (int i = 1; i <= n; i++) insert(t[i]);
	printf("%d\n", ans);
	return 0;
}