Massive Algorithms: Jobdu-1535-重叠的最长子串[扩展KMP]

九度-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，可以去看论文：《求最长回文子串与最长重复子串》何林的集训队论文

void getnext(char *T)
{
int k = 0;
int Tlen = strlen(T);
next[0] = Tlen;
while(k < Tlen-1 && T[k] == T[k+1])
k++;
next[1] = k;
k = 1;
for(int i = 2; i < Tlen; i++)
{
int p = k+next[k]-1, L = next[i-k]; // p :=已经匹配到的最远的位置
// L :=
if((i-1)+L >= p)
{
int j=(p-i+1)>0? p-i+1:0;
while(i+j < Tlen && T[k+j]==T[j])
j++;
next[i] = j;
k = i;
}
else next[k]=L;
}
}
void getextend(char *S,char *T)
{
int a = 0;
getnext(T);
int Slen = strlen(S);
int Tlen = strlen(T);
int len = Slen<Tlen ? Slen:Tlen;
while(a < len && S[a] == T[a]) a++;
extend[0] = a;
a = 0;
for(int i = 1; i < Slen; i++)
{
int p = a + extend[a]-1, L = next[i-a];
if(i+L-1 >= p)
{
int j = (p-i+1)>0? p-i+1:0;
while(i+j < Slen && j<Tlen && S[i+j] == T[j])
j++;
extend[i] = j;
a = i;
}
else extend[i] = L;
}
}

getextend(S,T);
int n = strlen(S);
int res = 0;
for(int i = 0; i < n; i++)
{
if(extend[i] == n-i)
{
res = extend[i];
break;
}
}
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

16int 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）的时间内求得所有位置的哈希值

int overlap(string &a,string &b)
{
int alen = a.size(), blen = b.size();
int res = 0;
ull ahash = 0, bhash = 0, t = 1;
for(int i = 1; i <= min(alen,blen); i++)
{
ahash = ahash + (a[alen-i]-'a')*t; //a的长度为i的后缀哈希值
bhash = bhash*B + b[i-1]-'a'; //b的长度为i的前缀哈希值
if(ahash == bhash) res = i;
t *= B;
}
return res;
}

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

int maxLen(const char* S, const char* T) {
int Slen = strlen(S), Tlen = strlen(T), i, j, minLen = min(Slen, Tlen), res = 0;
typedef unsigned long long ull;
ull Shash = 0, Thash = 0, t = 1, radix = 100000007;
for (int i = 1; i <= minLen; ++i) {
Shash = Shash + (S[Slen-i] - 'a') * t;
Thash = Thash * radix + (T[i-1] - 'a');
t *= radix;
if (Shash == Thash)
res = i;
}
return res;
}

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

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

Labels

Popular Posts