HDU 2594 Simpsons’ Hidden Talents KMP

题意：给你两个字符串s1,s2,让你求一个最大长度的子串t，t是s1的前缀，并且是s2的后缀，输出t和t的长度，如果不存在，直接输出0.

1、直接求next

#include <iostream>  
#include <cstdio>  
#include <cstdlib>  
#include <cmath>  
#include <cstring>  
#include <string>  
#include <vector>  
#include <list>  
#include <deque>  
#include <queue>  
#include <iterator>  
#include <stack>  
#include <map>  
#include <set>  
#include <algorithm>  
#include <cctype>  
using namespace std; 
 
typedef long long LL; 
const int N=50005; 
const LL II=100000000; 
const int INF=0x3f3f3f3f; 
const double PI=acos(-1.0); 
 
int next[2*N],len; 
char str[2*N],xh[N]; 
 
void getnext(char *p) 
{ 
    int j=0,k=-1; 
    next[0]=-1; 
    while(j<len)//len是p的长度  
    { 
        if(k==-1||p[j]==p[k]) 
        { 
            j++;    k++; 
            next[j]=k; 
        } 
        else 
            k=next[k]; 
    } 
} 
 
int main() 
{ 
    int i,j,T; 
    while(scanf("%s%s",str,xh)!=EOF) 
    { 
        int len1=strlen(str),len2=strlen(xh); 
        len=len1+len2; 
        strcat(str,xh); 
        getnext(str); 
        while(next[len]>len1||next[len]>len2) 
        { 
            len=next[len]; 
        } 
        str[next[len]]='\0'; 
        if(next[len]==0) 
            printf("0\n"); 
        else 
            printf("%s %d\n",str,next[len]); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;

typedef long long LL;
const int N=50005;
const LL II=100000000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);

int next[2*N],len;
char str[2*N],xh[N];

void getnext(char *p)
{
    int j=0,k=-1;
    next[0]=-1;
    while(j<len)//len是p的长度
    {
        if(k==-1||p[j]==p[k])
        {
            j++;    k++;
            next[j]=k;
        }
        else
            k=next[k];
    }
}

int main()
{
    int i,j,T;
    while(scanf("%s%s",str,xh)!=EOF)
    {
        int len1=strlen(str),len2=strlen(xh);
        len=len1+len2;
        strcat(str,xh);
        getnext(str);
        while(next[len]>len1||next[len]>len2)
        {
            len=next[len];
        }
        str[next[len]]='\0';
        if(next[len]==0)
            printf("0\n");
        else
            printf("%s %d\n",str,next[len]);
    }
    return 0;
}

2、KMP匹配，将s1作为模式串，将s2作为主串，直接kmp

#include <cstdio>  
#include <cstring>  
using namespace std; 
 
const int N = 50002; 
char str1[N]; 
char str2[N]; 
int next[N]; 
 
void get_next(int len_1); 
int kmp_search(int len_1, int len_2); 
 
int main() 
{ 
    int len; 
    while(scanf("%s%s", str1, str2) != EOF) 
    { 
        int len_1 = strlen(str1); 
        int len_2 = strlen(str2); 
        get_next(len_1); 
        len = kmp_search(len_1, len_2); 
        if(len == 0) 
        { 
            printf("0\n"); 
        } 
        else 
        { 
            for(int i = 0; i < len; i++) 
            { 
                printf("%c", str1[i]); 
            } 
            printf(" %d\n", len); 
        } 
    } 
    return 0; 
} 
 
void get_next(int len_1) 
{ 
    int i = 0; 
    int j = -1; 
    next[i] = -1; 
    while(i < len_1) 
    { 
        if(j == -1 || str1[j] == str1[i]) 
        { 
            i++; 
            j++; 
            if(str1[i] == str1[j]) 
            { 
                next[i] = next[j]; 
            } 
            else 
            { 
                next[i] = j; 
            } 
        } 
        else 
        { 
            j = next[j]; 
        } 
    } 
} 
 
int kmp_search(int len_1, int len_2) 
{ 
    int i = 0; 
    int j = 0; 
    while(i < len_2) 
    { 
        if(j == -1 || str1[j] == str2[i]) 
        { 
            i++; 
            j++; 
        } 
        else 
        { 
            j = next[j]; 
        } 
    } 
    if(j == -1) 
    { 
        return 0; 
    } 
    if(j == 0) 
    { 
        if(str1[0] == str2[len_2 - 1]) 
        { 
            return 1; 
        } 
        else 
        { 
            return 0; 
        } 
    } 
    else 
    { 
        return j; 
    } 
} 

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 50002;
char str1[N];
char str2[N];
int next[N];

void get_next(int len_1);
int kmp_search(int len_1, int len_2);

int main()
{
    int len;
    while(scanf("%s%s", str1, str2) != EOF)
    {
        int len_1 = strlen(str1);
        int len_2 = strlen(str2);
        get_next(len_1);
        len = kmp_search(len_1, len_2);
        if(len == 0)
        {
            printf("0\n");
        }
        else
        {
            for(int i = 0; i < len; i++)
            {
                printf("%c", str1[i]);
            }
            printf(" %d\n", len);
        }
    }
    return 0;
}

void get_next(int len_1)
{
    int i = 0;
    int j = -1;
    next[i] = -1;
    while(i < len_1)
    {
        if(j == -1 || str1[j] == str1[i])
        {
            i++;
            j++;
            if(str1[i] == str1[j])
            {
                next[i] = next[j];
            }
            else
            {
                next[i] = j;
            }
        }
        else
        {
            j = next[j];
        }
    }
}

int kmp_search(int len_1, int len_2)
{
    int i = 0;
    int j = 0;
    while(i < len_2)
    {
        if(j == -1 || str1[j] == str2[i])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if(j == -1)
    {
        return 0;
    }
    if(j == 0)
    {
        if(str1[0] == str2[len_2 - 1])
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else
    {
        return j;
    }
}

补充：软件开发 , C++ ,

上一个：SRM 585
下一个：hdu4300之KMP&&EKMP