首页 > ACM题库 > 九度OJ > 九度-1535-重叠的最长子串[解题代码]
2013
12-13

九度-1535-重叠的最长子串[解题代码]

题目描述:

给定两个字符串,求它们前后重叠的最长子串的长度,比如"abcde"和“cdefg”是"cde",长度为3。

输入:

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

输出:

对应每个测试案例,输出它们前后重叠的最长子串的长度。

样例输入:
abcde cdefg
样例输出:
3

cpp 代码如下:
#include"stdio.h"
#include"string.h"
#define M 1000010
int judge(char *s,char *t,int low,int high){
    int index_t = 0;
    int len_t = strlen(t);
    while(low <= high)
    {
        if(s[low] != t[index_t]) return 0;
        ++low;
        ++index_t;
    }
    return 1;
}

int main()
{
    char s[M],t[M];
    int len_s,len_t,i,flag;
    while(~scanf("%s%s",s,t))
    {
        flag = 0;
        len_s = strlen(s);
        len_t = strlen(t);
        i = len_s > len_t ? len_s-len_t : 0;//减少判断,s串短,从0开始判断,s串长,从len_s-len_t位置开始判断。
        for(; i < len_s ;++i)
        {
            if(s[i] == t[0] && judge(s,t,i,len_s -1))
            {
                printf("%d\n",len_s - i);
                flag = 1;
                break;
            }
        }
        if(!flag) printf("0\n");
    }
    return 0;
}
/**************************************************************
	Problem: 1535
	User: coder
	Language: C++
	Result: Accepted
	Time:200 ms
	Memory:2904 kb
****************************************************************/