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

K - Clairewd’s message HDU - 4300

The question ： Here you are. a-z The decrypted text of is a-z Encrypt the corresponding letters , Then I'll give you a string of numbers , The first half is encrypted and the second half is unencrypted but may not be complete , Let you find the smallest complete string .

analysis ： We can parse all the ciphertext , So the front part becomes the decrypted character , Then it becomes exkmp Find the longest prefix match .

#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;
}