hdu 1841 Find the Shortest Common Superstring

题目链接http://acm.hdu.edu.cn/showproblem.php?pid=1841

本题的意思就是给出两个字符串，看一下能组成最短的串的长度，当然只能首尾连接

这题也是对KMP的应用，主要还是对next数组的的求解

这题大概应该有两个地方需要注意的

1.开始写这题我直接就把串连接为S=S1+S2和S=S2+S1这两种情况，然后比较取S串最短的那种

比如样例中alba和bacau,则可以组成alba（ba）cau和串bacaualba显然前者组合方式可以取得最短串S

对于判断过程，则可以考察串s1的前缀和s2的后缀或者是s1的后缀和s2的前缀最大匹配程度，这个过程中就可以将他们连接到一个

串S中，求出S的next数组，进而判断他们的匹配程度。以上思路少考虑了一种情况，我在这里WA了一次，就是可能一个短串s1可能包含在长串s2

中，这种情况下只需要输出最长串的长度

2.第二个问题就是个小问题了，可能也就我会出现疏忽，就是在strcat(s1,s2)后，s1发生了改变，下次不能连接strcat(s2,s1),可以分别把它们另存一下，以便第二次连接

还有一个就是这题多次调用KMP函数getnext，开始对这点处理的很不好，写了好几个函数，后来学会传参数的时候把字符串对应的长度也传过去，就会减少不必要的麻烦

代码如下

View Code

 1 # include <stdio.h>
 2 # include <string.h>
 3 # define NN 1000001
 4 char s1[NN*2],s2[NN*2],s3[NN*2],s4[NN*2];
 5 int len1,len2,len;
 6 int next[NN*2];
 7 void getnext(char *P,int L)
 8 {
 9     int i=0,j=-1;
10     next[0]=-1;
11     while(i<L)
12     {
13         if(j==-1 || P[i]==P[j])
14         {
15             ++i;
16             ++j;
17             next[i]=j;
18         }
19         else j=next[j];
20     }
21 }
22 int KMP(char *S,char *P, int LS,int LP)
23 {
24     int i=0, j=0;
25     getnext(P,LP);
26     while(i<LS && j<LP)
27     {
28         if(j==-1 || S[i]==P[j])
29         {
30             ++i;
31             ++j;
32         }
33         else j=next[j];
34     }
35     if(j==LP) return 1;
36     return 0;
37 }
38 int main()
39 {
40     int t, flag;
41     scanf("%d",&t);
42     while(t--)
43     {
44         int sum1,sum2,k;
45         flag=0;
46         scanf("%s %s",s1,s2);
47         strcpy(s3,s1); //拷贝字符串以便在下面交换连接s1和s2
48         strcpy(s4,s2);
49         len1 = strlen(s1);
50         len2 = strlen(s2);
51         len = len1 + len2;
52 
53         if(len1 <= len2)     //这里判断长子串是否包含短子串
54         {
55             flag = KMP(s2,s1,len2,len1);
56             if(flag==1) printf("%d\n",len2);
57         }
58         else if(len1 > len2)
59         {
60             flag = KMP(s1,s2,len1,len2);
61             if(flag==1) printf("%d\n",len1);
62         }
63         if(flag==0) //这里对一般情况进行处理，即不是互相包含
64         {
65             strcat(s1,s2); //先将s2连接至s1
66             getnext(s1,len);
67             int k = len;
68             while(next[k]>len1 || next[k]>len2)
69                 k=next[k];
70             if(next[k]==0) sum1=len;
71             else
72             {
73                 sum1 = len-next[k];
74             }
75 
76             strcat(s4,s3);  //将s1连接至s2
77             getnext(s4,len);
78                 k = len;
79             while(next[k]>len1 || next[k]>len2)
80                 k=next[k];
81             if(next[k]==0) sum2=len;
82             else
83             {
84                 sum2 = len-next[k];
85             }
86             if(sum1<=sum2)
87                 printf("%d\n",sum1);
88             else printf("%d\n",sum2);
89         }
90     }
91     return 0;
92 }

另推荐一篇介绍KMP的文章，感觉很不错http://www.cnblogs.com/wentfar/archive/2011/12/17/2291340.html