1 // File Name: getnext.cpp 2 // Author: darkdream 3 // Created Time: 2014年09月09日 星期二 22时35分02秒 4  5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque>10 #include<stack>11 #include<bitset>12 #include<algorithm>13 #include<functional>14 #include<numeric>15 #include<utility>16 #include<sstream>17 #include<iostream>18 #include<iomanip>19 #include<cstdio>20 #include<cmath>21 #include<cstdlib>22 #include<cstring>23 #include<ctime>24 #define LL long long25 26 using namespace std;27 char str[50005];28 char str1[50005];29 int next[50005];30 int next1[50005];31 void getnext()32 {33     int len = strlen(str);34     int len1 = strlen(str1);35     next[0] = -1; 36     int k = -1;37     int j = 0 ;38     int sum = 0 ; 39     while(j <= len - 1 )40     {41         if(k == -1 || str[j] == str[k])42         {43             ++j; 44             ++k;45             next[j] = k ;46         }47         else {48             k = next[k];49         }50     }51     k = 0;52     j = 0 ; 53     while(j <= len1 -1)54     {55          if(k == -1 || str[k] == str1[j])56          {57            ++ j ; 58            ++ k ;59            next1[j] = k; 60          }else{61            k = next[k];62          }63     }64     /*for(int i = 0 ;i <= len1 ;i ++)65         printf("%d ",next1[i]);66     printf("\n");*/67     if(next1[len1] == 0)68         printf("0\n");69     else{70       for(int i = 0 ;i < next1[len1] ;i ++)71           printf("%c",str[i]);72       printf(" %d\n",next1[len1]);73     }74 }75 int main(){76     while(scanf("%s",str) != EOF)77     {78       scanf("%s",str1);79       getnext();80     }81     return 0;82 }