題目大意：
給字符串S，T， 找到所有的tetrad (a,b,c,d)， Sa..b + Sc..d = T , a≤b and c≤d.
其實就是把T分成兩段，這兩段都由S中的子串組成的，求有多少中組合方式（S中的兩個子串可重疊）。
分析與總結：
這題的AC是我最近幾天最高興的一個AC，因為dp題現在還做得少只會一些基本模型，對dp有種畏懼感，而這題就運用了dp的思想，結果亂搞搞出來了......
我的思路：
設T的長度為len， T可以有前綴T1，後綴T2。
按照長度來分類的話， T1的長度可以為1,2,3...len-1， 相應的T2的長度也可以為1,2,3..len-1。
假設有了一個長度為x的T1， 為了拼湊成完整的T，就要找一個長度為len-x的後綴T2。
那麼，在S中有子串T1，T2，cnt1【i】表示長度為i的T1的數量，同理cnt2【i】表示長度為i的T2的數量， 那麼，所有的拼湊方案就是 sum = cnt1[1]*cnt2[len-1]+cnt1[2]*cnt2[len-2]+....cnt[len-1]*cnt[1]。
知道了上述結論，那麼現在的關鍵就是求S中的各種長度的匹配串T1和T2的數量。
我的方法是用拓展KMP， 求出S中的所有後綴的與T的前綴最長公共子串長度，extend【i】表示S【i】開始的與T的前綴的最長公共串，根據這些長度，可以可以確定T1的數量。 假設S=“aabcde”, T="abcge", 那麼extend[0] = 1, extend[1]=3...
然後是求後綴T2， 可以把S和T全都轉置，倒過來存，然後用同樣的方法求出T2數量。
但是有了extend數組還不夠，需要求出所有長度的T1，T2數量，這一步就用了dp的思想。
我們可以知道：
extend[i] = 2時, 這個2同時也包含著1的串。
extend[i] = 3時，這個3同時也包含這2,1的串。
extend[i] = 4時，這個4同時也包含著3,2,1的串。
extend[i] = 5時，這個5同時也包含著4,3,2,1的串。
。。。
所以先直接把這些extend的數量先放到cnt裡，再這樣計算（實在不知道怎樣描述，就放代碼）：
[cpp]
for(int i=0; S[i]; ++i){
if(extend1[i]){
++cnt1[extend1[i]];
}
if(extend2[i]){
++cnt2[extend2[i]];
}
}
for(int i=len-1; i>=1; --i){
cnt1[i] += cnt1[i+1];
cnt2[i] += cnt2[i+1];
}
之後，就直接可以根據公式算出答案了。
代碼：
[cpp]
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long int64;
const int MAXN = 200005;
char S[MAXN];
char T[MAXN];
int f[MAXN];
int64 cnt1[MAXN], cnt2[MAXN];
int extend1[MAXN], extend2[MAXN];
void getNext(char* T,int* next){
int len=strlen(T), a=0;
next[0] = len;
while(a<len-1 && T[a]==T[a+1])++a;
next[1] = a;
a=1;
for(int k=2; k<len; ++k){
int p=a+next[a]-1, L=next[k-a];
if(k-1+L >= p){
int j=max(p-k+1,0);
while(k+j<len && T[k+j]==T[j]) ++j;
next[k] = j;
a=k;
}
else
next[k] = L;
}
}
void EKMP(char* S,char* P,int* next, int* extend){
getNext(P,next);
int slen=strlen(S), tlen=strlen(P), a=0;
int minlen=min(slen,tlen);
while(a<minlen && S[a]==T[a])++a;
extend[0] = a;
a=0;
for(int k=1; k<slen; ++k){
int p=a+extend[a]-1, L=next[k-a];
if(k-1+L >= p){
int j=max(p-k+1,0);
while(k+j<slen && j<tlen && S[k+j]==T[j]) ++j;
extend[k] = j;
a=k;
}
else
extend[k] = L;
}
}
int main(){
int nCase;
scanf("%d",&nCase);
while(nCase--){
memset(S, 0, sizeof(S));
memset(T, 0, sizeof(T));
scanf("%s %s",S,T);
EKMP(S,T,f,extend1);
int len=strlen(S);
for(int i=0,k=len-1; i<len/2; ++i,--k){
char ch=S[i];
S[i] = S[k];
S[k] = ch;
}
len=strlen(T);
for(int i=0, k=len-1; i<len/2; ++i,--k){
char ch=T[i];
T[i] = T[k];
T[k] = ch;
}
EKMP(S,T,f,extend2);
memset(cnt1, 0, sizeof(cnt1));
memset(cnt2, 0, sizeof(cnt2));
for(int i=0; S[i]; ++i){
if(extend1[i]){
++cnt1[extend1[i]];
}
if(extend2[i]){
++cnt2[extend2[i]];
}
}
for(int i=len-1; i>=1; --i){
cnt1[i] += cnt1[i+1];
cnt2[i] += cnt2[i+1];
}
long long ans=0;
for(int i=1; i<len; ++i)
ans += cnt1[i] * cnt2[len-i];
printf("%lld\n",ans);
}
return 0;
}
