首页 > ACM题库 > HDU-杭电 > HDU 1867 A + B for you again-KMP-[解题报告] C++
2013
12-23

HDU 1867 A + B for you again-KMP-[解题报告] C++

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;
}

     

解题报告转自:http://blog.csdn.net/xianxingwuguan1/article/details/12625593


,
  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;
    }