HDU 4300 Clairewd’s message (next函数的应用)

题意：给你一个明文对密文的字母表，在给你一段截获信息，截获信息前半段是密文，后半段是明文，但不清楚它们的分界点在哪里，密文一定是完整的，明文可能是残缺的，求完整的信息串（即完整的密文+明文串）。

题解：KMP next函数的应用。

#include <cstdio>

#include <cstring>

#include <cstdlib>

const int MAXN = ;

char table[];

char extable[];

char ori[MAXN];

char aft[MAXN];

int next[MAXN];

int  len;

void init()

{

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

        extable[ table[i]-'a' ] = 'a' + i;

    len = strlen(ori);

    for ( int i = ; i < len/; ++i )

        aft[i] = ori[i];

    for ( int i = len/; i < len; ++i )

        aft[i] = table[ ori[i] - 'a' ];

    aft[len] = '\0';

    return;

}

void getNext( char* s, int* next )

{

    int length = len;

    int i = , j = -;

    next[] = -;

    while ( i < length )

    {

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

        {

            ++i, ++j;

            next[i] = j;

        }

        else j = next[j];

    }

}

int main()

{

    int T;

    scanf( "%d", &T );

    while ( T-- )

    {

        scanf( "%s", table );

        scanf( "%s", ori );

        init();

        getNext( aft, next );

        int ans = len;

        //printf("next[%d] = %d\n", ans, next[ans] );

        while ( next[ans] > len/ ) ans = next[ans];

        ans = len - next[ans];

        //printf( "ans = %d\n", ans );

        for ( int i = ; i < ans; ++i )

            printf( "%c", ori[i] );

        for ( int i = ; i < ans; ++i )

            printf( "%c", extable[ ori[i] - 'a' ] );

        puts("");

    }

    return ;

}