题目大意：
给字符串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?
#include?
#include?
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 ??? next[1] = a;?
??? a=1;?
??? for(int k=2; 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 ??????????? 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 ??? extend[0] = a;?
??? a=0;?
??? for(int k=1; 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 ??????????? 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 ??????????? char ch=S[i];?
??????????? S[i] = S[k];?
??????????? S[k] = ch;?
??????? }?
??????? len=strlen(T);?
??????? for(int i=0, k=len-1; i ??????????? 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 ??????????? ans += cnt1[i] * cnt2[len-i];?
??????? printf("%lld\n",ans);?
??? }?
??? return 0;?
}?