HDU 4300 Clairewd’s message（扩展KMP）题解

题意：先给你一个密码本，再给你一串字符串，字符串前面是密文，后面是明文（明文可能不完成整），也就是说这个字符串由一个完整的密文和可能不完整的该密文的明文组成，要你找出最短的密文+明文。

思路：我们把字符串当做全是密文然后解密成明文，这样前面密文部分就是完整的明文，后面明文部分就乱码了，要求最短密文+明文就是求最短的密文，就是求原串和解密后的串的最大公共前缀，所以用EXMP求解。

坑爹了，前面没加‘\0’后面加了WA了一早上...orz

#include<cstdio>

#include<map>

#include<set>

#include<queue>

#include<cstring>

#include<string>

#include<cmath>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

const int maxn = 100000+5;

const int MOD = 10007;

const int INF = 0x3f3f3f3f;

using namespace std;

int Next[maxn],extend[maxn];

char trans[30],s1[maxn],s2[maxn];

char kk[30];

void getNext(char *x){

    int len = strlen(x);

    Next[0] = len;

    int j = 0;

    while(j + 1 < len && x[j] == x[j + 1]) j++;

    Next[1] = j;

    int k = 1;

    for(int i = 2;i < len;i++){

        int p = Next[k] + k - 1;

        int L = Next[i - k];

        if(i + L < p + 1)

            Next[i] = L;

        else{

            j = max(0,p - i + 1);

            while(i + j < len && x[i + j] == x[j]) j++;

            Next[i] = j;

            k = i;

        }

    }

}

void ExKMP(char *y,char *x){

   getNext(x);

   int j = 0;

   int lenx = strlen(x);

   int leny = strlen(y);

   while(j < leny && j < lenx && x[j] == y[j]) j++;

   extend[0] = j;

   int k = 0;

   for(int i = 1;i < leny;i++){

        int p = extend[k] + k - 1;

        int L = Next[i - k];

        if(i + L < p + 1)

            extend[i] = L;

        else{

            j = max(0,p - i + 1);

            while(i + j < leny && j < lenx && y[i + j] == x[j]) j++;

            extend[i] = j;

            k = i;

        }

   }

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%s%s",kk,s1);

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

            trans[kk[i] - 'a'] = i + 'a';   //密文转化为明文

        int len = strlen(s1);

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

            s2[i] = trans[s1[i] - 'a'];

        s2[len] = '\0';

        //printf("%s\n%s\n",s1,s2);

        ExKMP(s1,s2);

        //for(int i = 0;i < len;i++) printf("%d ",extend[i]);

        int i;

        for(i = 0;i < len;i++){

            if(i + extend[i] >= len && i >= extend[i]){

                break;

            }

        }

        len = len - extend[i];

        s1[len] = s2[len] = '\0';

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

    }

    return 0;

}