CodeForces 25E Test KMP

题目链接：点击打开链接

题意：

给定3个字符串，进行拼接

重复的一段可以覆盖，问拼接后最小的长度（若一个串s1是s2的子串，则s1可以认为嵌入了s2内，不需要进行拼接

思路：

kmp搞一下。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 300005 char T[N];//从0开始存 int f[N];//记录P的自我匹配 void getFail(int len, char *P) { int i = 0, j = -1; f[0] = -1; while(i != len) { if(j == -1 || P[i] == P[j]) f[++i] = ++j; else j = f[j]; } } int KMP(int *f2, char *S1, char *S2, int lens1, int lens2){ //f2是S2的失配数组 getFail(lens2, S2); int pos = 0, len = lens1, j = 0, i = 0; int gg = 0; while(i <= len) { while(j!=-1 && S1[i] != S2[j]) j = f2[j]; i++, j++; gg = max(j, gg); if(i == len) { pos = max(pos, j); } } if(gg == lens2)return gg; return pos; //这样得到的是S1的尾部和S2的前缀的 最大匹配位置（在S2中的位置） }/* */ char s[3][N/3]; char tmp[N]; int l[3]; int hehe(int a,int b,int c){ int pos = KMP(f, s[a], s[b], l[a], l[b]); for(int i = 0; i < l[a]; i++)tmp[i] = s[a][i]; int top = l[a]; if(pos!=l[b]) for(; pos