https://cn.vjudge.net/problem/2040809/origin
题意:在S串中找一个子串，在T串中找一个前缀，求拼起来是回文串的方案种数。
首先S串取出来的串可以分为s1 + s2,T串取出来的前缀为t,其中s1与t拼起来为回文串，s2本身为回文串
所以说对于s2,可以用马拉车预处理出S串中每个下标作为起点可以产生的回文串的数量。
对于s1可知s1的逆序与t相同，所以将S串翻转，用EXKMP求出每个后缀对t的LCP
最后两者贡献相乘就是答案。
赛后总结：
1.因为这题开在最大流和最小球覆盖后面，下意识认为应当是回文树或者后缀自动机才能做的字符串题，由于还没学到的原因产生了怯意
2.事实上开了一会儿之后发现并不是不可做，前一部分处理s2回文串的贡献在比赛的时候已经敲出来了，但是后一部分因为沉迷模拟样例aabbaa和aabb，S的逆序还是S，所以迷惑了做题的方法，下次应当自己搞一个比较普遍的样例、
3.总结起来 是字符串做的不够多
#include <map> #include <set> #include <ctime> #include <cmath> #include <queue> #include <stack> #include <vector> #include <string> #include <bitset> #include <cstdio> #include <cstdlib> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <functional> using namespace std; #define For(i, x, y) for(int i=x;i<=y;i++) #define _For(i, x, y) for(int i=x;i>=y;i--) #define Mem(f, x) memset(f,x,sizeof(f)) #define Sca(x) scanf("%d", &x) #define Sca2(x,y) scanf("%d%d",&x,&y) #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z) #define Scl(x) scanf("%lld",&x) #define Pri(x) printf("%d ", x) #define Prl(x) printf("%lld ",x) #define CLR(u) for(int i=0;i<=N;i++)u[i].clear(); #define LL long long #define ULL unsigned long long #define mp make_pair #define PII pair<int,int> #define PIL pair<int,long long> #define PLL pair<long long,long long> #define pb push_back #define fi first #define se second typedef vector<int> VI; int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();} while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;} const double PI = acos(-1.0); const double eps = 1e-9; const int maxn = 1e6 + 10; const int INF = 0x3f3f3f3f; const int mod = 1e9 + 7; int N,M,K; char S[maxn],T[maxn]; char Ma[maxn << 1]; int Mp[maxn << 1]; LL pre[maxn << 1],val[maxn]; LL nxt[maxn],extend[maxn]; void Manacher(char s[],int len){ int l = 0; Ma[l++] = '$'; Ma[l++] = '#'; for(int i = 0 ; i < len ; i ++){ Ma[l++] = s[i]; Ma[l++] = '#'; } Ma[l] = 0; int mx = 0,id = 0; for(int i = 0; i < l ; i ++){ Mp[i] = mx > i?min(Mp[2 * id - i],mx - i):1; while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++; if(i + Mp[i] > mx){ mx = i + Mp[i]; id = i; } } } void init(char* str,int l){ Manacher(str,l); for(int i = 0 ; i < l * 2 + 2; i ++){ //cout << i - (Mp[i] - 1) + 1 << endl; pre[i - (Mp[i] - 1) + 1]++; pre[i + 1]--; } int cnt = 0; for(int i = 1; i < l * 2 + 2; i ++){ pre[i] += pre[i - 1]; if(!(i & 1)){ val[cnt++] = pre[i]; // cout << cnt - 1 << " " << val[cnt - 1] << endl; } } // cout << l << " " << cnt <<endl; // for(int i = 0 ; i < l; i ++){ // cout << val[i] << endl; //} } void pre_EKMP(char x[],int m,LL next[]){ next[0] = m; LL j = 0; while(j + 1 < m &&x[j] == x[j + 1]) j ++; next[1] = j; LL k = 1; for(int i = 2; i < m ; i ++){ LL p = next[k] + k - 1; LL L = next[i - k]; if(i + L < p + 1) next[i] = L; else{ j = max(0LL,p - i + 1); while(i + j < m && x[i + j] == x[j]) j ++; next[i] = j; k = i; } } } void EKMP(char x[],int m,char y[],int n,LL next[],LL extend[]){ pre_EKMP(x,m,next); LL j = 0; while(j < n && j < m && x[j] == y[j]) j ++; extend[0] = j; LL k = 0; for(int i = 1; i < n ; i ++){ LL p = extend[k] + k - 1; LL L = next[i - k]; if(i + L < p + 1) extend[i] = L; else{ j = max(0LL,p - i + 1); while(i + j < n &&j < m && y[i + j] == x[j]) j++; extend[i] = j; k = i; } } } int main(){ //freopen("c.txt","r",stdin); scanf("%s%s",S,T); int l1 = strlen(S),l2 = strlen(T); //cout << l1 << " " << l2 <<endl; init(S,l1); reverse(S,S + l1); reverse(val,val + l1); EKMP(T,l2,S,l1,nxt,extend); LL ans = 0; for(int i = 1 ; i < l1; i ++){ // if(extend[i] <100)cout << extend[i] << " " << val[i - 1] << endl; ans += 1ll * extend[i] * val[i - 1]; // cout << ans <<endl; } Prl(ans); return 0; }