HDU 4300 Clairewd’s message（扩展KMP）

骑猪看日落 2022-06-10 14:29 161阅读 0赞

Clairewd is a member of FBI. After several years concealing in BUPT, she intercepted some important messages and she was preparing for sending it to ykwd. They had agreed that each letter of these messages would be transfered to another one according to a conversion table.  
Unfortunately, GFW(someone's name, not what you just think about) has detected their action. He also got their conversion table by some unknown methods before. Clairewd was so clever and vigilant that when she realized that somebody was monitoring their action, she just stopped transmitting messages.  
But GFW knows that Clairewd would always firstly send the ciphertext and then plaintext(Note that they won't overlap each other). But he doesn't know how to separate the text because he has no idea about the whole message. However, he thinks that recovering the shortest possible text is not a hard task for you.  
Now GFW will give you the intercepted text and the conversion table. You should help him work out this problem.

Input

The first line contains only one integer T, which is the number of test cases.  
Each test case contains two lines. The first line of each test case is the conversion table S. S\[i\] is the ith latin letter's cryptographic letter. The second line is the intercepted text which has n letters that you should recover. It is possible that the text is complete.

*Hint*

Range of test data:  
T<= 100 ;  
n<= 100000;

Output

For each test case, output one line contains the shorest possible complete text.

Sample Input

2
    abcdefghijklmnopqrstuvwxyz
    abcdab
    qwertyuiopasdfghjklzxcvbnm
    qwertabcde

Sample Output

abcdabcd
    qwertabcde

题解：

题意：

话说这个我看了好久。。翻了好几篇博客终于看懂

给你一个暗文对明文的表（注意是暗文对明文）

然后给你一个字符串，这个串前半部分是暗文，后半部分是明文，暗文是全部的文字，而明文只有一部分，要你输出最短的暗文+明文字符串

思路：

这个有点绕，要举例来说，比如第二个样例，暗文对明文表是：qwertyuiopasdfghjklzxcvbnm

然后给的字符串是qwertabcde

由于题目说的暗文是给足了的，明文不足，所以明文至多是从该字符串一半的位置开始的，所以我们就先将前一半翻译成明文

比如qwert翻译过来，q-->a w-->b e-->c r->d....以此类推，是不是很奇怪的推法

然后因为现在的字符串我们有了前一半是明文，后一半部分是明文，那么我们就用KMP搞出next数组的值，要是要求的字符串长度最短，那么暗文部分长度就应该是字符串总长len-next\[len\],然后输出的明文用暗文翻译过去就好了

还有一个坑，不看别人的博客还不知道，比如串全部是由一个字符组成的aaa，那么假如表是abcdefg。。。。那么答案应该是aaaa，这个要特判一下

代码：

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<stdio.h>
    #include<math.h>
    #include<string>
    #include<stdio.h>
    #include<queue>
    #include<stack>
    #include<map>
    #include<vector>
    #include<deque>
    using namespace std;
    #define lson k*2
    #define rson k*2+1
    #define M (t[k].l+t[k].r)/2
    #define INF 1008611111
    #define ll long long
    #define eps 1e-15
    char T[100005];
    char intab[30];
    char p[30];
    int Next[100005];
    char a[100005];
    void init()
    {
        int i=0,j=-1;
        Next[0]=-1;
        while(T[i])
        {
            if(j==-1||T[j]==T[i])
            {
                i++;
                j++;
                Next[i]=j;
            }
            else
                j=Next[j];
        }
    }
    int main()
    {
        int i,j,len,test,d;
        scanf("%d",&test);
        while(test--)
        {
            scanf("%s",p);
            scanf("%s",a);
            len=strlen(a);
            d=(len-1)/2;
            strcpy(T,a);
            for(i=0;i<26;i++)//暗文对照明文转成明文对照暗文
            {
                intab[p[i]-'a']='a'+i;
            }
            for(i=0;i<=d;i++)
            {
                T[i]=intab[a[i]-'a'];
            }
            init();
            if(Next[len]==len-1&&T[0]==T[1])
            {
                for(i=0;i<((len+1)/2)*2;i++)
                    printf("%c",T[0]);
            }
            else
            {
                for(i=0;i<len-Next[len];i++)
                {
                    printf("%c",a[i]);
                }
                for(i=0;i<len-Next[len];i++)
                {
                    printf("%c",intab[a[i]-'a']);
                }
            }
            printf("\n");
        }
        return 0;
    }