題意：
????? 給你兩個(gè)字符串，讓你求str1+str2,就是把1的后面和2的前面重疊的地方只顯示一遍就行了 abc + bcd = abcd,要求和的長(zhǎng)度最小，和最小的前提下求字典序最小，還有就是兩個(gè)串可以交換位置的，cdab + abcd = abcdab 而不是 cdabcd,交換位置后合并是最短并且字典序最小的。

?

?

思路：
????? 首先得到兩個(gè)next數(shù)組，然后用str1 去匹配 str2,再用str2 去匹配str1，（因?yàn)榭梢越粨Q），分別得到子串走到最后時(shí)匹配串的位置，x,y,這個(gè)位置也就是重合了多少個(gè)，如果x == y說明無論誰在前前面，匹配后的長(zhǎng)度都是 l1 + l2 - x（或者 l1 + l2 - y ,x 和 y是相等的）,這樣我們把字典序小的那個(gè)放在前面，另一個(gè)把前面的x個(gè)字母去掉后接到字典序小的那個(gè)串的后面。如果x != y，如果x > y 當(dāng)然是按照大的那個(gè)匹配方式輸出了。因?yàn)橐蟮氖呛偷拈L(zhǎng)度最小。

?

#include<stdio.h>
#include<string.h>

#define N 100000 + 100

int next_a[N] ,next_b[N];
char str_a[N] ,str_b[N];

void get_next(char str[] ,int next[])
{
??? int j ,k ,m;
??? m = strlen(str);
??? j = 0 ,k = -1;
??? next[0] = -1;
??? while(j < m)
??? {
??????? if(k == -1 || str[j] == str[k])
??????? next[++j] = ++k;
??????? else
??????? k = next[k];
???? }
???? return;
}
???????
int KMP(char str1[] ,char str2[] ,int next[])
{
??? int n ,m ,i ,j;
??? n = strlen(str1);
??? m = strlen(str2);
??? for(i = j = 0 ;i < n ;)
??? {
??????? if(str1[i] == str2[j])
??????? {
?????????? i ++ ,j ++;
??????? }
??????? else
??????? {
??????????? j = next[j];
??????????? if(j == -1)
??????????? {
??????????????? j = 0;
??????????????? i ++;
??????????? }
??????? }
???? }
???? return j;
}

int main ()
{
??? while(~scanf("%s %s" ,str_a ,str_b))
??? {
??????? get_next(str_a ,next_a);
??????? get_next(str_b ,next_b);
??????? int x = KMP(str_a ,str_b ,next_b);
??????? int y = KMP(str_b ,str_a ,next_a);
??????? if(x == y)
??????? {
???????????? if(strcmp(str_a ,str_b) <= 0)
???????????? printf("%s%s\n" ,str_a ,str_b + x);
???????????? else
???????????? printf("%s%s\n" ,str_b ,str_a + x);
???????? }
???????? else
???????? {
???????????? if(x > y)
???????????? printf("%s%s\n" ,str_a ,str_b + x);
???????????? else
???????????? printf("%s%s\n" ,str_b ,str_a + y);
???????? }
??? }
??? return 0;
}
???????
????

總結(jié)

以上是生活随笔為你收集整理的hdu 1867 求两个串的和最小 ，KMP的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。