字符串匹配。kmp.
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int maxn=100010;
char tran[26],s[maxn];
int next[maxn];
void getv(char * t)//求失配函数
{
int i,j;strlen
int m=(t);
next[0]=-1;
i=0;j=-1;
while(i<m-1)
{
if(j==-1||t[i]==t[j])
{
j++;i++;
if(t[j]==t[i]) next[i]=next[j];
else next[i]=j;
}
else j=next[j];
}
}
int kmp(char * s1,char * s2)
{
int m=strlen(s1),n=strlen(s2);
int i=0,j=0;
while(i<m)
{
if(j==-1||s1[i]==s2[j])
{
i++;j++;
}
else j=next[j];
}
return j;
}
int main()
{
int t;
cin>>t;
char s1[maxn],s2[maxn];
while(t--)
{
getchar();
int i;
char c;
for(i=0;i<26;i++)
{
scanf("%c",&c);
tran[c-'a']=i+'a';
}
getchar();
scanf("%s",&s);
int m=strlen(s);
for(i=0;i<(m+1)/2;i++) s1[i]=tran[s[i]-'a'];
s1[i]='\0';
getv(s1);
int j;
for(j=0;j<m/2;j++) s2[j]=s[i+j];s2[j]='\0';
int ou=kmp(s2,s1);
for(i=0;i<m-ou;i++) printf("%c",s[i]);
for(i=0;i<m-ou;i++) printf("%c",tran[s[i]-'a']);
printf("\n");
}
return 0;
}