Clairewd’s message--hdu4300（Next数组的运用）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4300

题意就是给你26的字母的加密方式，然后又给了一个串s1是包含加密后的和没有加密的但是没有加密的可能不齐全；求完整的密文和原文；

例如第二个例子：

　　　　　　abcdefghijklmnopqrstuvwxyz

加密方式：  qwertyuiopasdfghjklzxcvbnm

　　s1：   qwertabcde

在s1中qwert就是密文，后面的abcde就是原文；

假如加密方式不变，s1变成qwertabc，那么答案还是qwertabcde；

密文的长度肯定大于s1总长度的一半，我们可以把s1前一半当成密文后一半不变，然后解密得到s2，那么s2的Next【len】就是给出的明文的长度，总长度-明文

的长度得到的就是密文的总长度，然后输出密文和密文对应的明文就可以了；

在串中加一个*是为了防止求多了匹配；（错了好多次）

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;

const int N = 2e5+7;
char s[27], s1[N], s2[N], s3[N], pass[27], ans[N];
int Len, Next[N], L;
void GetNext(char a[])
{
    int i=0, j=-1;
    Next[0] = -1;
    while(i<Len+1)
    {
        if(j==-1 || a[i] == a[j])
            Next[++i] = ++j;
        else
            j = Next[j];
    }
}

int main()
{
    int T, i;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%s%s", s, s1);
        for(i=0; i<26; i++)
            pass[s[i]-'a'] = 'a'+i;
        Len = strlen(s1);
        L = (Len + 1)/2;
        for(i=0; i<L; i++)
            s2[i] = pass[s1[i]-'a'];
        s2[i] = '*';
        s2[i+1]='';///不写的画下面没法用strcat;
        strcat(s2, s1+L);
        ///printf("%s
", s2);
        GetNext(s2);
        L = Len - Next[Len+1];
        for(i=0; i<L; i++)
        {
            ans[i] = s1[i];
            ans[i+L] = pass[s1[i]-'a'];
        }
        ans[i+L] = '';
        printf("%s
", ans);
    }
    return 0;
}