HDU 1867 A + B for you again (KMP)

时间:2023-01-03 17:06:39

个人觉得,KMP算法中,讲得最容易懂的是Matrix67那个版本:http://www.matrix67.com/blog/archives/115/

这道题的意思是,给两个字符串a和b,问a和b是否可以连接,求连接后长度最短的,在最短的条件下,再取字典序最小的。比如样例中的asdf和sdfg,可以连接成asdfg和sdfgasdf,明显前者才是符合要求的答案。

要找长度最短的,自然是有两种连接方式,一是a在前b在后,二是b在前a在后。a在前时,拿b去匹配a,求出把a完全匹配完后,b达到的位置即可。比如asdf和sdfg,把a匹配完,即sdf匹配了,返回的是g这个位置。把两种情况都计算一下,匹配得字符越多的肯定越优,因为可以把两者连起来后更短。若两种情况得到的长度相同,则比较a和b的字典序。

同时要注意asdf和sd这种情况,根据题意,这个连起来的答案是asdfsd,而不是asdf。即连接时,某串不能嵌入到另一串中间。故匹配的时候(假设b去匹配a),满足题意的应该是a匹配完了,但b还没完,或者a和b都匹配完了(比如asdf和sdf,答案是asdf)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define SIZE 100010
int next[SIZE];
char a[SIZE],b[SIZE];

void getNext(char *p)
{
    next[0] = -1;
    int k = -1;
    int len = (int)strlen(p);
    for(int i=1; i<len; i++)
    {
        while(k > -1 && p[k+1] != p[i])
            k = next[k];
        if(p[k+1] == p[i])
            ++k;
        next[i] = k;
    }
}

int KMP(char *s,char *p)
{
    getNext(p);
    int lenp = (int)strlen(p);
    int lens = (int)strlen(s);
    int k = -1,i = 0;
    for(i=0; i<lens && k+1<lenp; i++)
    {
        while(k > -1 && p[k+1] != s[i])
            k = next[k];
        if(p[k+1] == s[i])
            ++k;
    }
    if(k +1 < lenp || (k+1 == lenp && i == lens))
        return k+1;
    return 0;
}

int main()
{
    while(~scanf("%s%s",a,b))
    {
        int la = KMP(a,b);
        int lb = KMP(b,a);
        if(la > lb || (la == lb && strcmp(a,b) < 0))
        {
            printf("%s",a);
            printf("%s",b+la);
        }
        else
        {
            printf("%s",b);
            printf("%s",a+lb);
        }
        puts("");
    }
}