HDU 2594 最长相同前后缀

Sample Input
clinton
homer
riemann
marjorie

Sample Output
0
rie 3

输入两个字符串，求最长相同前后缀
直接把两个字符串连接在一起求next就行了，唯一要注意的就是长度不能大于原来任一字符串的长度，如果长度大于了，要选择len1和len2中较小的一个输出。

 1 # include <cstdio>
 2 # include <cstring>
 3 using namespace std ;
 4 
 5 char s1[100010] ;
 6 char s2[50010] ;
 7 char s3[50010] ;
 8 int next[100010] ;
 9 int len1 , len2; 
10 
11 void getNext()
12 {
13     int j, k;
14     j = 0; k = -1; next[0] = -1;
15     while(j < len1+len2)
16         if(k == -1 || s1[j] == s1[k])
17             next[++j] = ++k;
18         else
19             k = next[k];
20 }
21 
22 
23 int main ()
24 {
25     while (scanf("%s%s" , &s1 , &s2) != EOF)
26     {
27         len1 = strlen(s1) ;
28         len2 = strlen(s2) ;
29         strcat(s1 , s2) ;
30         getNext() ;
31         int i ;
32         for (i = 0 ; i < next[len1 + len2] ; i++)
33         {
34             s3[i] = s1[i] ;
35         }
36         s3[i] = '' ;
37         if (next[len1 + len2]) 
38         {
39             if (next[len1 + len2] > len1 ||next[len1 + len2] > len2)
40             {
41                 if (len1 > len2)
42                     printf("%s %d
" ,s2 ,len2) ;
43                 else
44                     {
45                         s3[len1] = '' ;
46                         printf("%s %d
" ,s3 ,len1) ;
47                     }
48             }
49             else
50               printf("%s %d
" ,s3 ,next[len1 + len2]) ;
51         }
52         else
53            printf("0
") ;
54     }
55     
56     
57     return 0 ;
58 }

View Code