Jobdu-1535-重叠的最长子串[扩展KMP] | Acm之家

九度-1535-重叠的最长子串[扩展KMP] | Acm之家
给定两个字符串，求它们前后重叠的最长子串的长度，比如"abcde"和"cdefg"是"cde"，长度为3。

对于每个测试案例只有一行， 包含两个字符串。字符串长度不超过1000000，仅包含字符’a'-’z'。

X.  KMP
http://arc9.riaos.com/?p=5077
http://blog.csdn.net/a1dark/article/details/16994887
咋一看貌似KMP扩展、其实只需要普通的KMP就可以解决、不过需要重新构造一个新字符串C=B+A、于是求出字符串C的next值、最后的值便是answer、
abcde cdefg
==> s3: cdefgabcde, use MKP to compute next or failure function.

int getnext(){
    int j=0,k=-1;
    next[0]=-1;
    int len=strlen(str3);
    while(j<len){
        if(k==-1||str3[j]==str3[k]){
            j++;
            k++;
            next[j]=k;
        }
        else k=next[k];
    }
    int ans=0;
    ans=min(len1,len2);
    ans=min(ans,k);
    return ans;
}

        len1=strlen(str1);
        len2=strlen(str2);
        memset(str3,'',sizeof(str3));
        for(int i=0;i<len2;i++){
            str3[i]=str2[i];
        }
        for(int i=len2,j=0;i<len1+len2,j<len1;i++,j++){
            str3[i]=str1[j];
        }

X. KMP Extended http://blog.csdn.net/xiaozhuaixifu/article/details/12348123

扩展KMP，用extend[i]保存 主串 S[i.....n-1]与 模式串 T的最长公共前缀的长度，其中n是S的长度。

然后扫描一遍 extend[] 如 extend[i] == n-i 那么这个后缀的长度就是我们要求的值。

关于扩展KMP，可以去看论文：《求最长回文子串与最长重复子串》何林 的集训队论文

1. void getnext(char *T)    
2. {    
3.     int k = 0;    
4.     int Tlen = strlen(T);   
5.     next[0] = Tlen;    
6.     while(k < Tlen-1 && T[k] == T[k+1])   
7.         k++;   
8.     next[1] = k;    
9.       
10.     k = 1;  
11.     for(int i = 2; i < Tlen; i++)    
12.     {    
13.         int p = k+next[k]-1, L = next[i-k];   // p :=已经匹配到的最远的位置  
14.                                             // L :=     
15.         if((i-1)+L >= p)    
16.         {    
17.             int j=(p-i+1)>0? p-i+1:0;    
18.             while(i+j < Tlen && T[k+j]==T[j])   
19.                 j++;    
20.             next[i] = j;    
21.             k = i;    
22.         }    
23.         else next[k]=L;    
24.     }    
25. }    
26.     
27. void getextend(char *S,char *T)    
28. {    
29.     int a = 0;    
30.     getnext(T);    
31.     int Slen = strlen(S);    
32.     int Tlen = strlen(T);    
33.     int len = Slen<Tlen ? Slen:Tlen;    
34.     while(a < len && S[a] == T[a]) a++;    
35.     extend[0] = a;    
36.     a = 0;    
37.     for(int i = 1; i < Slen; i++)    
38.     {    
39.         int p = a + extend[a]-1, L = next[i-a];    
40.           
41.         if(i+L-1 >= p)  
42.         {    
43.             int j = (p-i+1)>0? p-i+1:0;    
44.               
45.             while(i+j < Slen && j<Tlen && S[i+j] == T[j])   
46.                 j++;    
47.             extend[i] = j;    
48.             a = i;    
49.         }    
50.         else extend[i] = L;    
51.     }    
52. }  

1.         getextend(S,T);  
2.         int n = strlen(S);  
3.         int res = 0;  
4.         for(int i = 0; i < n; i++)  
5.         {  
6.             if(extend[i] == n-i)  
7.             {  
8.                 res = extend[i];  
9.                 break;  
10.             }  
11.         }  
12.         cout<<res<<endl; 

X. Brute Force

int judge(char *s,char *t,int low,int high){

05	int index_t = 0;

06	int len_t = strlen(t);

07	while(low <= high)

08

{

09	if(s[low] != t[index_t]) return 0;

10

++low;

11	++index_t;

12

}

13

return 1;

14

}

15

16	int main()

17

{

18	char s[M],t[M];

19	int len_s,len_t,i,flag;

20	while(~scanf("%s%s",s,t))

21

{

22

flag = 0;

23	len_s = strlen(s);

24	len_t = strlen(t);

25	i = len_s > len_t ? len_s-len_t : 0;//减少判断，s串短，从0开始判断，s串长，从len_s-len_t位置开始判断。

26	for(; i < len_s ;++i)

27

{

28	if(s[i] == t[0] && judge(s,t,i,len_s -1))

29

{

30	printf("%d\n",len_s - i);

31

flag = 1;

32

break;

33

}

34

}

35	if(!flag) printf("0\n");

36

}

37

return 0;

38

}

X. Rolling Hash
http://blog.csdn.net/xiaozhuaixifu/article/details/12348123

下面介绍一种滚动哈希算法：假设要求S的后缀和T的前缀相等的最大长度，也可以利用滚动哈希在O（n+m）的时间内求解：
假设字符串C = c1c2....cm 定义哈希函数：
H(C) = (c1*b^(m-1)+c2*b^(m-2)+.....+cm*b^(0)) mod h ，
其中 b和h是两个互素的数，这样，我们就可以将字符串 S=s1s2...sn 从位置 k+1 开始长度为m的 子串 S[k+1....k+m]的哈希值
根据 子串 S[k....k+m-1]的哈希值在常数
时间内求出来：
H(S[k+1....k+m]) = H(S[k..k+m-1]*b - sk*b^m +s(k+m)) mod h ，
只要不断这样右移，就可以在O（n）的时间内求得所有位置的哈希值

1. int overlap(string &a,string &b)  
2. {  
3.     int alen = a.size(), blen = b.size();  
4.     int res = 0;  
5.     ull ahash = 0, bhash = 0, t = 1;  
6.     for(int i = 1; i <= min(alen,blen); i++)  
7.     {  
8.         ahash = ahash + (a[alen-i]-'a')*t; //a的长度为i的后缀哈希值  
9.         bhash = bhash*B + b[i-1]-'a';     //b的长度为i的前缀哈希值  
10.         if(ahash == bhash) res = i;  
11.         t *= B;   
12.     }  
13.     return res;  
14. } 

http://blog.csdn.net/taoqick/article/details/38470057

1. int maxLen(const char* S, const char* T) {  
2.   int Slen = strlen(S), Tlen = strlen(T), i, j, minLen = min(Slen, Tlen), res = 0;  
3.   typedef unsigned long long ull;  
4.   ull Shash = 0, Thash = 0, t = 1, radix = 100000007;  
5.     
6.   for (int i = 1; i <= minLen; ++i) {  
7.     Shash = Shash + (S[Slen-i] - 'a') * t;  
8.     Thash = Thash * radix + (T[i-1] - 'a');      
9.     t *= radix;  
10.     if (Shash == Thash)  
11.       res = i;  
12.   }  
13.   return res;  
14. } 

Read full article from 九度-1535-重叠的最长子串[扩展KMP] | Acm之家