zoj 3587 Marlon's String(拓展KMP+dp)
题目大意：
给字符串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;
}
