HDU 1867 A + B for you again ----KMP

题意:

给你两个字符串,输出他们合并之后的字符串,合并的时候把A的后缀和B的前缀重叠合(或者把A的前缀和B的后缀重合)。要求合并后的串既包含A右包含B,

且使得合并后的字符串尽量短,其次是使得合并后的字符串字典序尽量小.

分析:

首先A和B合并他们一定是首尾重叠相连,要求合并后字典序最小,所以当合并后串长度一样时,我们要把A或B中字典序小

  的放在前面。

然后计算A的后缀和B的前缀匹配长度为len1,计算A的前缀和B的后缀匹配长度为len2。

如果len1大,那么就把A放前面。如果len2大,那么就把B放前面。

关键点:

  求字符串匹配长度

hdu G++ 提交

#include "bits/stdc++.h"

可以
#include "bits/stdc++.h"
using namespace std; const int maxn=; int next1[maxn];
char s1[maxn],s2[maxn]; void getnext(char *t){
int len=strlen(t);
int i=,j=-;
next1[]=-;
while(i<len){
if(j==- || t[i]==t[j]){
i++;j++;
next1[i]=j;
}else
j=next1[j];
}
} int KMP(char *s,char *t){
int len1=strlen(s),len2=strlen(t);
int i=,j=;
getnext(t);
while(i<len1 && j<len2){
if(j==- || s[i]==t[j]){
i++;j++;
}else
j=next1[j];
}
if(i==len1)
return j;
return ;
}
///KMP返回的就是那个公共子串的长度
int main(){ //freopen("input.txt","r",stdin);
while(~scanf("%s%s",s1,s2)){
int x=KMP(s1,s2);///s1模式串
int y=KMP(s2,s1);
if(x==y){///相等取字典序小的
if(strcmp(s1,s2)<)
printf("%s%s\n",s1,s2+x);
else
printf("%s%s\n",s2,s1+x);
}else if(x>y)///取合并后短的
printf("%s%s\n",s1,s2+x);
else
printf("%s%s\n",s2,s1+y);
}
return ;
}
上一篇:python之模块datetime 常见操作


下一篇:objective-c 语法快速过(2)