HDU 1867 KMP

题意：

求str1 的最长后缀与 str2 的最长前缀。使得 str1+str2 的长度最小，并且字典序最小（str1和str2可以互换）

题解：

kmp的p数组的含义：p[i]表示以i为结尾的字符串最多和开头匹配的个数。也正是这道题求解的关键、

具体做法就是将两个字符串合并处理求一下p数组就好了~

ps：合并的时候中间一定要加“分隔符”（比如：#，@之类的~），否则会有惊喜。。。

abcbcbca bcbcbc 对拍了半天才发现这个bug。。。

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #include <algorithm>
 6 
 7 #define N 2001000
 8 
 9 using namespace std;
10 
11 int lena,lenb,lenc;
12 int p[N];
13 char str1[N],str2[N],c[N];
14 
15 inline void getp()
16 {
17     p[1]=0;
18     for(int i=2,len=0;i<=lenc;i++)
19     {
20         while(len>0&&c[i]!=c[len+1]) len=p[len];
21         if(c[i]==c[len+1]) len++;
22         p[i]=len;
23     }
24 }
25 
26 inline int getlen(char a[],char b[])
27 {
28     lena=strlen(a+1);
29     lenb=strlen(b+1);
30     lenc=lena+lenb+1;
31     for(int i=1;i<=lenb;i++) c[i]=b[i];
32     c[1+lenb]='#';
33     for(int i=1;i<=lena;i++) c[i+lenb+1]=a[i];
34     getp();
35     return p[lenc];
36 }
37 
38 inline void go()
39 {
40     int len1=getlen(str1,str2);
41     int len2=getlen(str2,str1);
42     if(len1==len2)
43     {
44         if(strcmp(str1+1,str2+1)<0) printf("%s%s",str1+1,str2+len1+1);
45         else printf("%s%s",str2+1,str1+len2+1);
46     }
47     else if(len1<len2) printf("%s%s",str2+1,str1+len2+1);
48     else printf("%s%s",str1+1,str2+len1+1);
49     puts("");
50 }
51 
52 int main()
53 {
54     while(scanf("%s%s",str1+1,str2+1)!=EOF) go();
55     return 0;
56 }