Problem Statement
You are given a string $S$ consisting of lowercase English letters. Print the number of non-empty strings $T$ that satisfy the following condition, modulo $998244353$.
The concatenation $TT$ of two copies of $T$ is a subsequence of $S$ (not necessarily contiguous).
Constraints
- $S$ is a string consisting of lowercase English letters whose length is between $1$ and $100$, inclusive.
Input
The input is given from Standard Input in the following format:
$S$
Output
Print the answer.
Sample Input 1
ababbaba
Sample Output 1
8
The eight strings satisfying the condition are a, aa, ab, aba, b, ba, bab, and bb.
Sample Input 2
zzz
Sample Output 2
1
The only string satisfying the condition is z.
Note that this string contributes to the answer just once, although there are three ways to extract the subsequence zz from $S = S_1S_2S_3 = $ zzz: $S_1S_2 = $ zz, $S_1S_3 = $ zz, and $S_2S_3 = $ zz.
Sample Input 3
ppppqqppqqqpqpqppqpqqqqpppqppq
Sample Output 3
580
考虑枚举两个串的开头，就设为 \(a\) 和 \(b\)，满足 \(s_a=s_b\),然后分别跳子序列自动机。
为了使所有跳的操作不重复，我们应该强制第一个串的开头就是某个字母的第一次出现。
然后进行dp，定义 \(dp_{i,j}\) 为第一个串目前跳的到了点 \(i\)，第二个串跳到了点 \(j\) 的情况。当然，要满足 \(i<a\)
理论上，要把所有的 \(dp_{i,j}\) 全部计入答案。但是我们发现如果这样会算重。比如串 ababab，那么枚举第一个 a时，会把 ab 这个串数两次。去一下重就可以了。如果 \(i\) 的下一个 \(s_a\) 的出现地方时 \(b\)，那么我们才计入答案。
复杂度：枚举两个串开头是 \(O(n)\) 的，dp \(O(|\Sigma|n^2)\)，总复杂度 \(O(n^3|\Sigma|)\)
#include<bits/stdc++.h>
using namespace std;
const int N=105,P=998244353;
int n,nx[N][26],dp[N][N],ans;
char s[N];
void add(int&x,int y)
{
x=x+y>=P? x+y-P:x+y;
}
int main()
{
scanf("%s",s+1),n=strlen(s+1);
for(int i=n-1;i>=1;i--)
{
memcpy(nx[i],nx[i+1],sizeof(nx[i]));
nx[i][s[i+1]-'a']=i+1;
}
// printf("%d\n",nx[1][0]);
for(int i=0;i<26;i++)
{
int st=0;
for(int j=1;j<=n;j++)
{
if(s[j]-'a'^i)
continue;
if(!st)
st=j;
else
{
// printf("hjh:%d %d\n",st,j);
memset(dp,0,sizeof(dp));
dp[st][j]=1;
for(int a=st;a<j;a++)
{
for(int b=j;b<=n;b++)
{
// if(dp[a][b])
// printf("%d %d\n",a,b);
if(nx[a][i]==j)
add(ans,dp[a][b]);
for(int c=0;c<26;c++)
if(nx[a][c]<j&&nx[a][c]&&nx[b][c])
add(dp[nx[a][c]][nx[b][c]],dp[a][b]);
}
}
}
}
// add(ans,(bool)st);
}
printf("%d",ans);
}