HDU 4300 Clairewd‘s message 拓展KMP入门
题意
这个题关键是要读懂题意，我做的时候就没有读懂，泪。题意是说给你的一个两个字符串，一个是26个字母密码表，依次对应替换的字母。然后给你一个字符串，这个字符串是不完整的（完整的应该是前半部分是加密的，后半部分是解密了的），然而，给你的字符串一定是加密的部分+一部分解密的部分（可以是全部，也可以是没有），让你求出最短的完整字符串，包括密文和明文；
解题思路
考虑给出的字符串S加密部分一定全部给出，所以给出的字符串的一半（最少是一半的长度）一定是加密的，也就是说给的字符串s = 密文+明文，我们把s全部按照密文进行转换得到字符串T =明文+密文，这样我们进行拓展KMP，S作为母串，T作为子串（虽然他俩一样长），这样我们求S串的位置i处的extend[i]值，看看是不是等于len(S)-i(也就是S串左边的那部分长度，其实就是我们假设的密文长度)。
我也是看的题解做的这个题，看完后知道了，这个题难度不难，就是题意不好懂，理解后其实就是个拓展KMP的模板题，害，谁让自己太菜了呢？
代码实现
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
#define hash hs //因为c++中hash好像是个特殊的标识符，但是下面我用了hash，这样改正比较简单
using namespace std;
const int MAXN=1e5+7;
int nx[MAXN], extend[MAXN];
char hash[27], op[27], str1[MAXN], str2[MAXN];
int t, n;
void get()
{
int a=0, p=0, m=n;
nx[0]=m;
for(int i=1; i<m; i++)
{
if(i>=p || i+nx[i-a] >=p)
{
if(i>=p)
p=i;
while(p<m && str2[p] == str2[p-i])
p++;
nx[i] = p - i;
a = i;
}
else nx[i] = nx[i-a];
}
}
void getextend()
{
int a=0, p=0;
get();
for(int i=0; i<n; i++)
{
if(i>=p || i+nx[i-a]>=p)
{
if(i>=p)
p=i;
while(p<n && p-i<n && str1[p] == str2[p-i])
p++;
extend[i] = p-i;
a = i;
}
else extend[i] = nx[i-a];
}
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%s %s", op, str1);
for(int i=0; i<26; i++)
hash[ op[i]-'a' ] = i + 'a';
n = strlen(str1);
for(int i=0; i<n; i++)
str2[i] = hash[ str1[i]-'a' ];
getextend();
int div=n;
for(int i=(n+1)/2; i < n; i++)
{
if(extend[i] == n - i && i >=extend[i])
{
div=i;
break;
}
}
for(int i=0; i<div; i++)
printf("%c", str1[i]);
for(int i=0; i<div; i++)
printf("%c", str2[i]);
printf("
");
}
return 0;
}