HDU-1841-Find the Shortest Common Superstring（kmp）

个人博客

题目链接

题意：

给出两个串，用这两个串组成一个新串，使新串包含这两个串，问这个新串的长度最小是多少；

题解：

显然，对于两个串A，B；A如果是B的子串或者B如果是A的子串的话，直接输出那个母串的长度即可，如果没有这种关系，那么看一个串的后缀是否是另一个串的前缀，如果某个串的后缀与另一个串的前缀的公共部分最长，则答案=A.length+B.length-公共长度，所以可以直接用kmp去做。(kmp匹配最后j值为模式串前缀和主串后缀最长公共长度)

代码：

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<cstring> 
using namespace std; 
const int N = 1000100;
char a[3][2*N];
int fail[2*N];
inline int max(int a, int b){
    return (a > b) ? a : b;
}
int kmp(int &i, int &j, char* str, char* pat){
    int k;
    memset(fail, -1, sizeof(fail));
    for (i = 1; pat[i]; ++i){
        for (k = fail[i - 1]; k >= 0 && pat[i] != pat[k + 1]; k = fail[k]);
        if (pat[k + 1] == pat[i]){
            fail[i] = k + 1;
        }
    }
    i = j = 0;
    while (str[i] && pat[j]){
        if (pat[j] == str[i]){
            i++;
            j++;
        }
        else if (j == 0){
            i++;    
        }
        else{
            j = fail[j - 1] + 1;
        }
    }
    //printf("%d %d\n",i,j);
    if (pat[j]){
        return -1;
    }
    else{
        return i - j;
    }
}
int main(int argc, const char * argv[]){
    int T;
    scanf("%d", &T);
    while (T--){
        int i, j, l1 = 0, l2 = 0;
        cin >> a[0] >> a[1];
        int len1 = (int)strlen(a[0]), len2 = (int)strlen(a[1]), val;
        val = kmp(i, j, a[1], a[0]);            
        if (val != -1){
            l1 = len1;
        }
        else{
            if (i == len2 && j - 1 >= 0 && a[1][len2 - 1] == a[0][j - 1]){
                l1 = j;
            }
        }
        val = kmp(i, j, a[0], a[1]);           
        if (val != -1){
            l2 = len2;
        }
        else{
            if (i == len1 && j - 1 >= 0 && a[0][len1 - 1] == a[1][j - 1]){
                l2 = j;
            }
        }
        printf("%d\n", len1 + len2 - max(l1, l2));
    }
    return 0;
}