hdu 2594

////  main.cpp//  KMP////  Created by liuzhe on 16/7/16.//  Copyright © 2016年 my_code. All rights reserved.//#include <iostream>#include <algorithm>#include <string>#include <cstring>#include <cstdio>using namespace std;#define Size 50002char s1[Size],s2[Size];int anext[Size];int len1,len2;void get_next(){    int i,j;    i=0;    j=-1;    anext[0]=-1;    while(i<len1)    {        if(j==-1||s1[i]==s1[j])        {            i++;            j++;            anext[i]=j;        }        else            j=anext[j];    }}void kmp(){    int i,j;    i=0;    j=0;    while(i<len2)    {        if(j==-1||s1[j]==s2[i])        {            i++;            j++;        }        else            j=anext[j];    }    if(!j) // 匹配不了        PRintf("%d/n",j);    else    {        for(int k=0;k<j;k++) // 在s1中前j个字符就是共同最长的            printf("%c",s1[k]);        printf(" %d/n",j);    }}int main(){    while(scanf("%s %s",s1,s2)!=EOF) // 题目要求最长的s1的前缀同时满足是s2的后缀    {        len1=strlen(s1); // 可以反过来想一下，把s2作为主串，s1为子串        len2=strlen(s2); // 然后s1不断往后移动，匹配之后就可以了        get_next();        kmp();    }    return 0;}