hdu 4300 Clairewd’s message KMP应用

Clairewd’s message

题意:先一个转换表S，表示第i个拉丁字母转换为s[i],即a -> s[1];(a为明文，s[i]为密文)。之后给你一串长度为n<= 100000的前面为密文后面为明文的串；让你通过密码转换表S在这个串的后面添加字符，使得前面的密文翻译成明文之后与后面相对应，最后输出添加字符后的串(前面密文照常输出)；

Sample Input

2

abcdefghijklmnopqrstuvwxyz

abcdab

qwertyuiopasdfghjklzxcvbnm

qwertabcde

 

Sample Output

abcdabcd

qwertabcde

 

思路:既然前面的密文部分是确定的，并且后面明文的长度不超出整个输入串长度的1/2;这样只需将前面的密文转化为明文，kmp之后，直接按照最后一个字符进行匹配，要求能匹配的长度在前半串之内，这样就找到了输入的明文对应的前缀字符串。同时知道了中间缺少的长度，这样再次使用转换表S即可~~

坑点:里面最大的长度为2倍的输入串..并且HDU现在貌似MLE归为TLE了..

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N = 2e5 + ;

char p[N],T[N],t[],s[];

int f[N];

void getfail(char *p,int *f)

{

    f[] = f[] = ;

    int n = strlen(p);

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

        int j = f[i];

        if(j && p[i] != p[j]) j = f[j];

        f[i+] = (p[i] == p[j] ?j+:);// ｉ＋１会递推到第ｎ位

    }

}

int main()

{

    int kase;

    scanf("%d",&kase);

    while(kase--){

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

        int n = strlen(s),m = strlen(p)/,len = strlen(p);

        for(int i = ;i < n;i++) t[s[i]-'a'] = 'a'+i; // 密文->明文;

        for(int i = ;i < m;i++) T[i] = t[p[i]-'a']; // 前半部分密文转为明文;

        for(int i = m;i < len;i++) T[i] = p[i];

        getfail(T,f);

        int id = ;

        for(int j = f[len];j;j = f[j]){

            if(j <= m){

                id = j;

                break;

            }

        }

        int dif = len-id-id;// 减去能匹配的就是中间没有转化的密文的长度

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

            p[len+i] = t[p[id+i]-'a'];

        }

        p[len+dif] = '\0';

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

    }

}