hdu 4300 Clairewd’s message kmp匹配！ 多校联合赛第一题
题目大意是有一份文件，前面是密文，后面是原文，但那个人接到这个文件后不知道中间从哪里开始是原文，所以你要帮忙还原一下，如果后面原文比密文少，你就将它补全
字符串长度范围是100000如果是爆搜，n^2一定超时的没话说，但我比赛的时候好像是让驴踢了，套一层for循环枚举中间值，然后kmp，那kmp还不如暴力快了呢！！而且时间复杂都还是n^2,啊！！太缺了，将线段a以中间为标记分成两个数组前一半tay和后一般tey，在将tey后面添上一个len长度的‘*',作为标记，然后一tay为模式串，tey为原串，kmp其中‘*’就是万能匹配符，之后的mid+kmp(tay,tey)就是密文长度！！
#include<iostream>#include<string.h>#include<cstdio>#include<memory>using namespace std;#define N 100005char a[N*3],b[30],tey[N*3],tay[N*3],len;int pa[30],next[N*3];void prenext(char str[]){ int j=-1,i; next[0]=-1; int len1=strlen(str); for(int i=1;i<len1;i++){ while(j>=0&&str[j+1]!=str[i]) j=next[j]; if(str[j+1]==str[i]) j++; next[i]=j; }}int kmp(char str[],char str1[]){ int j=-1; int len1=strlen(str1); for(int i=0;str[i];i++){ while(j>=0&&str1[j+1]!=str[i]&&str[i]!='*') j=next[j]; if(str1[j+1]==str[i]||str[i]=='*') j++; if(j==len1-1) return i-j; } return 0;}int main(){// freopen("in.txt","r",stdin); int n; scanf("%d",&n); while(n--){ int sign=0; scanf("%s%s",b,a); for(int i=0;b[i];i++) pa[b[i]-'a']='a'+i; int len=strlen(a); int mid=(len+1)/2; for(int i=0;i<mid;i++){ tay[i]=pa[a[i]-'a']; } tay[mid]=0; int j=0; for(int i=mid;i<len;i++,j++) tey[j]=a[i]; for(;j<=2*len;j++) tey[j]='*'; tey[j]=0; prenext(tay); int t=mid+kmp(tey,tay); for(int i=0;i<t;i++) printf("%c",a[i]); for(int i=0;i<t;i++) printf("%c",pa[a[i]-'a']); cout<<endl; } return 0;}