CODEFORCES 25E Test

题意

三个字符串，找一个字符串（它的子串含有以上三个字符串）使它的长度最短，输出此字符串的长度。

---

题解

先枚举字符串排列，直接KMP两两匹配，拼接即可。。。答案取最小值。。

---

常数巨大的丑陋代码

# include <stdio.h>

# include <stdlib.h>

# include <iostream>

# include <string.h>

# include <algorithm>

using namespace std;

# define IL inline

# define RG register

# define UN unsigned

# define ll long long

# define rep(i, a, b) for(RG int i = a; i <= b; i++)

# define per(i, a, b) for(RG int i = b; i >= a; i--)

# define mem(a, b) memset(a, b, sizeof(a))

# define max(a, b) ((a) > (b)) ? (a) : (b)

# define min(a, b) ((a) < (b)) ? (a) : (b)

# define Swap(a, b) a ^= b, b ^= a, a ^= b;

const int MAXN = 100001;

int len, nt[MAXN], cnt = 2147483647;

char ans[MAXN*3];

IL void KMP(RG char s[]){

    RG int l = strlen(s), j = 0;

    mem(nt, 0);

    rep(i, 1, l - 1){

        while(j && s[i] != s[j]) j = nt[j-1];

        if(s[i] == s[j]) j++;

        nt[i] = j;

    }

    j = 0;

    rep(i, 0, len-1){

        while(j && ans[i] != s[j]) j = nt[j-1];

        if(ans[i] == s[j]) j++;

        if(j == l) return; //少了这个会WA!!!

    }

    while(j < l) ans[len++] = s[j++];

}

IL void Work(RG char s1[], char s2[], char s3[]){

    len = strlen(s3);

    rep(i, 0, len-1) ans[i] = s3[i];

    KMP(s1); KMP(s2);

    cnt = min(cnt, len);

}

int main(){

    char ss1[MAXN], ss2[MAXN], ss3[MAXN];

    scanf(" %s %s %s", ss1, ss2, ss3);

    Work(ss1, ss2, ss3);

    Work(ss1, ss3, ss2);

    Work(ss2, ss1, ss3);

    Work(ss2, ss3, ss1);

    Work(ss3, ss1, ss2);

    Work(ss3, ss2, ss1);

    printf("%d\n", cnt);

    return 0;

}