2013
12-23

# A + B for you again

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.

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.

Print the ultimate string by the book.

asdf sdfg
asdf ghjk

asdfg
asdfghjk

题目链接如下：http://acm.hdu.edu.cn/showproblem.php?pid=1867

题意：将两个字符串加在一起，重复的部分只出现一次，长度越短优先，字典序越短优先，

思路：kmp 求出两个字符串做为各自字串kmp值，kmp有修改；

代码：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<stack>
#include<queue>
#include<list>
#include<string>
using namespace std;
const int maxn=222222;
int next[maxn];
void getnext(char x[])
{
int i,j;
int m=strlen(x);
j=next[0]=-1;
i=0;
while(i<m)
{
while(j!=-1&&x[i]!=x[j])j=next[j];
next[++i]=++j;
}
}
int kmp(char s[],char t[])
{
int n=strlen(s);
int m=strlen(t);
getnext(t);
int i,j;
for(i=0,j=0;i<n&&j<m;)
{
if(j==-1||s[i]==t[j])
++i,++j;
else j=next[j];
}
if(i>=n)return j;
return 0;
}
int main()
{
char s[maxn],t[maxn];
for(; ~scanf("%s%s",s,t);)
{
int x=kmp(s,t);
int y=kmp(t,s);
if(x==y)
{
if(strcmp(s,t)>0)
{
printf("%s",t);
printf("%s\n",s+x);
}
else
{
printf("%s",s);
printf("%s\n",t+x);
}
}
else if(x>y)
{
printf("%s",s);
printf("%s\n",t+x);
}
else
{
printf("%s",t);
printf("%s\n",s+y);
}
}
return 0;
}

1. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}