首页 > ACM题库 > HDU-杭电 > HDU 1841 Find the Shortest Common Superstring-KMP-[解题报告] C++
2013
12-23

HDU 1841 Find the Shortest Common Superstring-KMP-[解题报告] C++

Find the Shortest Common Superstring

问题描述 :

The shortest common superstring of 2 strings S1 and S2 is a string S with the minimum number of characters which contains both S1 and S2 as a sequence of consecutive characters. For instance, the shortest common superstring of “alba” and “bacau” is “albacau”.
Given two strings composed of lowercase English characters, find the length of their shortest common superstring.

输入:

The first line of input contains an integer number T, representing the number of test cases to follow. Each test case consists of 2 lines. The first of these lines contains the string S1 and the second line contains the string S2. Both of these strings contain at least 1 and at most 1.000.000 characters.

输出:

For each of the T test cases, in the order given in the input, print one line containing the length of the shortest common superstring.

样例输入:

2
alba
bacau
resita
mures

样例输出:

7
8

hdu 1841

这题很简单,两次kmp,每次调用kmp算法返回的都是串s1的最大后缀和s2的最大前缀

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

using namespace std;

const int maxn=1000010;
char s1[maxn],s2[maxn];
int next[maxn];

void get_next(char *s,int len)
{
    next[0]=-1;
    int i=0,j=-1;
    while(i<len)
    {
        if(j==-1||s[i]==s[j]) next[++i]=++j;
        else j=next[j];
    }
}
int kmp(char *t1,char *t2)
{
    int len1=strlen(t1);
    int len2=strlen(t2);
    get_next(t2,len2);
    int i=0,j=0;
    while(i<len1&&j<len2)
    {
        if(j==-1||t1[i]==t2[j]) ++i,++j;
        else j=next[j];
    }
    return j;
}

int main()
{
    int ca;
    scanf("%d",&ca);
    while(ca--)
    {
        scanf("%s %s",s1,s2);
        int l1=kmp(s1,s2);
        int l2=kmp(s2,s1);
        printf("%d\n",strlen(s1)+strlen(s2)-max(l1,l2));
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/struggle_mind/article/details/7769475


,
  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  2. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?