Clairewd’s message - HDU 4300（next[]运用）

题目大意：给两个串第一个串是翻译表（密文可以通过翻译表翻译成明文），第二个串是由密文+明文组成，前面是密文（完整的），后面是明文（未必完整），问能不能把第二个串补全，输出最短的一种可能。

 

分析：题意比较抽象...拿第二个例子来说吧，

qwertabcde-> qwert是密文，abcde是明文，密文可以通过上面的qwertyuiopasdfghjklzxcvbnm（26个字母，每个字母变成它所在的下标的字母q->a） 翻译成后面的明文，这么看应该明白怎么回事了吧。然后知到要求出来短的补全，要使补全最短的话，那么就要求出来后缀前缀的最大相等值是多少，然后把未匹配的补全就行了比如第一组数据 abcdab 为了防止匹配超过一半（因为密文是不缺少的，所以密文最少也得占一半），在中间的位置加一个‘*’分割,变成了 abc*dab 很明显最后的最大匹配度就是 2 ，也就是后面的两个是明文，前面的都是密文

代码如下：

=============================================================================================================

#include<stdio.h>

#include<string.h>

const int MAXN = 2e5+;

const int oo = 1e9+;

const int mod = ;

char s[MAXN], a[MAXN], pass[MAXN];

int next[MAXN];

void GetNext(char s[], int N)

{

    int i=, j=-;

    next[] = -;

    while(i < N)

    {

        if(j==- || s[i]==s[j])

            next[++i] = ++j;

        else

            j = next[j];

    }

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int i, N, Mid;

        scanf("%s%s", s, a);

        for(i=; s[i]; i++)

        {

            pass[ s[i]-'a' ] = i+'a';

        }

        N = strlen(a);

        Mid = (N+)/;

        for(i=; i<Mid; i++)

            s[i] = pass[ a[i]-'a' ];

        s[i] = '*', s[i+]=;

        strcat(s, a+i);

        GetNext(s, N+);

        Mid = N-next[N+];

        for(i=; i<Mid; i++)

        {

            s[i] = a[i];

            s[i+Mid] = pass[ a[i]-'a' ];

        }

        s[i+Mid] = ;

        printf("%s\n", s);

    }

    return ;

}