N3verL4nd

# A + B for you again

Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2989    Accepted Submission(s): 730

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

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#pragma warning(disable : 4996)
int Next[100005];
void get_next(char *B, int m)
{
char pat[100005] = {0};
strcpy(pat + 1, B);
Next[1] = 0;
int i, j = 0;
for(i = 2; i <= m; i++)
{
while(j > 0 && pat[j+1] != pat[i])
{
j = Next[j];
}
if(pat[j+1] == pat[i])
{
j += 1;
}
Next[i] = j;
}
}
int kmp(char *A, char *B)
{
char text[100005] = {0};
char pat[100005] = {0};
strcpy(text + 1, A);
strcpy(pat + 1, B);
int n = strlen(text + 1);
int m = strlen(pat + 1);
get_next(B, m);
int i, j = 0;
for(i = 1; i <= n; i++)
{
while(j > 0 && pat[j+1] != text[i])
{
j = Next[j];
}
if(pat[j+1] == text[i])
{
j += 1;
}
if(i == n)
{
return j;
}
}
return 0;
}
int main()
{
freopen("in.txt", "r", stdin);
char text[100005], pat[100005];
int x, y;
while(scanf("%s%s", text + 1, pat + 1) != EOF)
{
x = kmp(text + 1, pat + 1);
y = kmp(pat + 1, text + 1);
//	cout << x << " " << y << endl;
if(x == y)
{
if(strcmp(text + 1, pat + 1) > 0)
{
printf("%s", pat + 1);
printf("%s\n", text + x + 1);
}
else if(strcmp(text + 1, pat + 1) < 0)
{
printf("%s", text + 1);
printf("%s\n", pat + x + 1);
}
else
{
printf("%s\n", text + 1);
}
}
else if(x > y)
{
printf("%s", text + 1);
printf("%s\n", pat + x + 1);
}
else
{
printf("%s", pat + 1);
printf("%s\n", text + y + 1);
}
}
}这个模版好搓=。=

#include <iostream>
#include <cstring>
#include <cstdio>
const int N=100001;
using namespace std;
int nextt[N];
void next(char s[])
{
int i=1,j=0;
int len=strlen(s);
nextt[0]=-1;
while(i<len)
{
if(j==-1||s[i]==s[j])
{
++i;
++j;
if(s[i]!=s[j])
nextt[i]=j;
else
nextt[i]=nextt[j];
}
else
j=nextt[j];
}
}
int kmp(char ss[],char s[])
{
int len1=strlen(ss);
int len2=strlen(s);
next(s);
int i=0,j=0;
while(i<len1&&j<len2)
{
if(j==-1||ss[i]==s[j])
{
++i;
++j;
}
else
j=nextt[j];
}
if(i==len1)
return j;
return 0;
}
int main()
{
char str1[N],str2[N];
while(~scanf("%s%s",str1,str2))
{
int x=kmp(str1,str2);
int y=kmp(str2,str1);
if(x==y)
{
if(strcmp(str1,str2)>0)
{
printf("%s",str2);
printf("%s\n",str1+x);
}
else
{
printf("%s",str1);
printf("%s\n",str2+x);
}
}
else if(x>y)
{
printf("%s",str1);
printf("%s\n",str2+x);
}
else
{
printf("%s",str2);
printf("%s\n",str1+y);
}
}
return 0;
}

``````

© 著作权归作者所有

### N3verL4nd

HDOJ 1009 FatMouse' Trade

FatMouse' TradeTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 81301 Accepted Submission(s): 28137 Problem Description FatM......

Dear_Jia
2017/09/30
0
0

my_sunshine26
2017/05/26
0
0
HDOJ 1811 Rank of Tetris

Rank of TetrisTime Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 11206 Accepted Submission(s): 3206 Problem Description 自从L......

dear_jia
2018/04/18
0
0
HDOJ4548美素数

zhagoodwell
2017/12/11
0
0

——这篇文章主要想总结下区间DP的经典题目，同时给自己复习巩固这方面知识点。 区间DP 一、定义 区间DP，顾名思义是在区间上DP，它的主要思想就是先在小区间进行DP得到最优解，然后再利用小...

my_sunshine26
2017/08/13
0
0

OSChina 周四乱弹 —— 当你简历注水但还是找到了工作

Osc乱弹歌单（2019）请戳（这里） 【今日歌曲】 @花间小酌 ：#今日歌曲推荐# 分享成龙的单曲《男儿当自强》。 《男儿当自强》- 成龙 手机党少年们想听歌，请使劲儿戳（这里） @hxg2016 ：刚在...

2.9K
22

5
0

cs平台

12
0

69
0

32
0