本文共 1885 字，大约阅读时间需要 6 分钟。

链接：

题目大意：

给字符串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里，再这样计算（实在不知道怎样描述，就放代码）：

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];        }

代码：

#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
      
       = p){            int j=max(p-k+1,0);            while(k+j
       
        = p){            int j=max(p-k+1,0);            while(k+j
        
         =1; --i){ cnt1[i] += cnt1[i+1]; cnt2[i] += cnt2[i+1]; } long long ans=0; for(int i=1; i
        
       
      
     
    
   

          原创  ， By   D_Double  (转载请标明)