首页 > 代码库 > HDU 1867 A + B for you again（KMP算法的应用）
HDU 1867 A + B for you again（KMP算法的应用）
A + B for you again
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4496 Accepted Submission(s): 1157
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
题意讲解： 给你两个字符串 s1，s2让你把它们，连接起来前后相同的重合一起，不再输出；
连接规则：
假设 s1 + s2 能匹配的长度为 len1 ；
s2 + s1 能匹配的长度为 len2 ；
如果 len1 = len2 判断谁在前就要看谁得字典序小了，当然小的在前
如果 len1 > len2 输出匹配后的字符串 s1+s2
如果 len1 < len2 输出匹配后的字符串 s2+s1
所以AC代码如下：略长
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #include<string> 7 #include<cmath> 8 using namespace std; 9 const int N = 1e5+10; 10 char s1[N],s2[N]; 11 int next[2][N],len1,len2; 12 int x1,x2; 13 void solve1(int len1)//寻找第一个字符串的next数组 14 { 15 int i = 0; 16 int j = -1; 17 next[0][0] = -1; 18 while(i<len1) 19 { 20 if(j== -1 || s1[i] == s1[j]) 21 { 22 ++i; 23 ++j; 24 next[0][i] = j; 25 } 26 else 27 { 28 j = next[0][j]; 29 } 30 } 31 } 32 void solve2(int len2)//寻找第二个字符串的next数组 33 { 34 int i = 0; 35 int j = -1; 36 next[1][0] = -1; 37 while(i<len2) 38 { 39 if(j== -1 || s2[i] == s2[j]) 40 { 41 ++i; 42 ++j; 43 next[1][i] = j; 44 } 45 else 46 { 47 j = next[1][j]; 48 } 49 } 50 } 51 int solve(char *s3,char *s4,int len,int x) //xx：表示字符串s3和s4匹配时，是从s3的第xx个开始匹配的 52 { 53 int j=0,i=0; 54 int xx=0; 55 while(i<len) 56 { 57 if(j==-1 || s3[i] == s4[j]) 58 { 59 i++; 60 j++; 61 } 62 else 63 { 64 j = next[x][j]; 65 xx=i-j; 66 } 67 } 68 return xx; 69 } 70 int main() 71 { 72 while(~scanf("%s %s",s1,s2)) 73 { 74 memset(next,-1,sizeof(next)); 75 len1 = strlen(s1); 76 len2 = strlen(s2); 77 solve1(len1); 78 solve2(len2); 79 int x1 = solve(s1,s2,len1,1); 80 int x2 = solve(s2,s1,len2,0); 81 //判断能匹配字符串的长度 82 int xx1 = len1 - x1; 83 int xx2 = len2 - x2; 84 //当s1在前或者s2在前连接的字符串总长度是相同的，则要按照字典序小的在前， 85 //例如：s1：abcefg s2：efgabc 都能匹配对方三个，所以要按照字典序abcefg 在前； 86 if(xx1 == xx2) 87 { 88 if(strcmp(s1,s2)<0) 89 { 90 for(int i=0; i<x1; i++) 91 printf("%c",s1[i]); 92 printf("%s\n",s2); 93 } 94 else 95 { 96 for(int i=0; i<x2; i++) 97 printf("%c",s2[i]); 98 printf("%s\n",s1); 99 }100 }101 //接下来就看，谁能匹配谁的多了，xx1 表示s2匹配s1 的长度，xx2表示 s1 匹配 s2的长度；102 //例如s1: abcdef s2: hjabcd ;这时s2，在前先输出；反之s1在前；103 else if(xx1 > xx2)104 {105 for(int i=0; i<x1; i++)106 printf("%c",s1[i]);107 printf("%s\n",s2);108 109 }110 else111 {112 for(int i=0; i<x2; i++)113 printf("%c",s2[i]);114 printf("%s\n",s1);115 }116 }117 return 0;118 }
HDU 1867 A + B for you again（KMP算法的应用）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。