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