admin管理员组文章数量:1642437
点击打开链接
Problem Description
Generally speaking, there are a lot of problems about strings processing. Now you encounter another such problem. If you get two strings, such as “asdf” and “sdfg”, the result of the addition between them is “asdfg”, for “sdf” is the tail substring of “asdf” and the head substring of the “sdfg” . However, the result comes as “asdfghjk”, when you have to add “asdf” and “ghjk” and guarantee the shortest string first, then the minimum lexicographic second, the same rules for other additions.Input
For each case, there are two strings (the chars selected just form ‘a’ to ‘z’) for you, and each length of theirs won’t exceed 10^5 and won’t be empty.Output
Print the ultimate string by the book.Sample Input
asdf sdfg asdf ghjk
Sample Output
asdfg asdfghjk
解题思路:题目就是字符串模式匹配,注意一些细节问题就可以了。但是java写的就是无限超内存,今天心情不好,再交,就过了,这是无语了啊
import java.util.*;
class P1867{
static int[] next=new int[100005];
public static void main(String args[]){
int n,m,i,len1,len2;
String str1,str2;
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
str1=sc.next();
str2=sc.next();
len1=str1.length();
len2=str2.length();
n=kmp(str1,str2);
m=kmp(str2,str1);
if(n==m){
if(str1pareTo(str2)>0){
System.out.println(str2+str1.substring(n,len1));
}else{
System.out.println(str1+str2.substring(n,len2));
}
}else if(n>m){
System.out.println(str1+str2.substring(n,len2));
}else{
System.out.println(str2+str1.substring(m,len1));
}
}
}
public static void set_next(String str){
int i=0,j=-1;
next[0]=-1;
int len=str.length();
while(i<len){
if(j==-1||str.charAt(i)==str.charAt(j)){
i++;
j++;
next[i]=j;///System.out.print(next[i]+" ");
}else{
j=next[j];
}
}
//System.out.println();
}
public static int kmp(String str1,String str2){
int i=0,j=0;
int len1=str1.length(),len2=str2.length();
set_next(str2);
while(i<len1){//System.out.print(j+" ");
if(j==-1||(j<len2&&str1.charAt(i)==str2.charAt(j))){
i++;
j++;//System.out.print("** ");
}else{
j=next[j];
}//System.out.print(j+"* ");
}//System.out.println();
if(i==len1){
return j;
}
return 0;
}
}
版权声明:本文标题:【KMP】hdu1867(A + B for you again) 杭电java a题真坑 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729340653a1197493.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论