K - Clairewd’s message HDU - 4300 （EXKMP）

K - Clairewd’s message HDU - 4300

题意：给你a-z的解密文即a-z加密对应的字母，然后给你一串数，前半部分是加密过的后半部分未加密过但可能不完整，让你求最小的完整的字符串。

分析：我们可以将密文全部解析，这样前面部分就变成解密后的字符，接下来就变成了exkmp找到最长前缀匹配。

#include <iostream>
#include <cstdio>
#include <stack>
#include <cmath>
#include <set>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 200100;

int t;
char ch[30];
char x[maxn], y[maxn], h[maxn], str[maxn];
int m, n, next1[maxn], extend[maxn];

void pre_EKMP(int m)
{
    next1[0] = m;
    int j = 0;
    while(j + 1 < m && x[j] == x[j + 1]) j++;
    next1[1] = j;
    int k = 1;
    for(int i = 2; i < m; i++)
    {
        int p = next1[k] + k - 1;
        int L = next1[i - k];
        if(i + L < p + 1) next1[i] = L;
        else{
            j = max(0, p - i + 1);
            while(i + j < m && x[i + j] == x[j]) j++;
            next1[i] = j;
            k = i;
        }
    }
}

void EKMP(int m, int n)
{
    pre_EKMP(m);
    int j = 0;
    while(j < n && j < m && x[j] == y[j]) j++;
    extend[0] = j;
    int k = 0;
    for(int i = 1; i < n; i++){
        int p = extend[k] + k - 1;
        int L = next1[i - k];
        if(i + L < p + 1) extend[i] = L;
        else{
            j = max(0, p - i + 1);
            while(i + j < n && j < m && y[i + j] == x[j]) j++;
            extend[i] = j;
            k = i;
        }
    }
}

int main()
{
    scanf("%d", &t);
    while(t--)
    {
        scanf("%s%s", &ch, &y);
        for(int i = 0; i < 26; i++)
            h[ch[i]] = i + 'a';
        int len = strlen(y);
        memset(x, 0, sizeof(x));
        for(int i = 0; i < len; i++)
            x[i] = h[y[i]];
        EKMP(len, len);
        int max1 = len;
        for(int i = 0; i < len; i++)
            if(i + extend[i] >= len && i >= extend[i])
            {
                max1 = i;
                break;
            }
        memset(str, 0, sizeof(str));
        for(int i = 0; i < max1; i++)
        {
            str[i] = y[i];
            str[i + max1] = h[y[i]];
        }
        puts(str);
    }
    return 0;
}