简单KMP,下面是官方题解
这道题问的就是将1个串如何变为stringA+stringB的形式,使得stringA是stringB经过映射得到相同的串。映射那步其实没有什么价值,假设str为原串s经过映射后得到的串,我们可以以str为模式串,以s为原串做一次扩展KMP,得到extend数组,extend[i]表示原串以第i开始与模式串的前缀的最长匹配。经过O(n)的枚举,我们可以得到,若extend[i]+i=len且i>=extend[i]时,表示stringB即为该点之前的串,stringA即为该点之前的str串,最后输出即可。
我的代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
using namespace std;
char s[30];
char q[30];
char inter[100010];
char cry[50010];
int p[100010];
int cnt[100010];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int i,j;
scanf("%s%s",s,inter);
for(i=0;s[i];i++)
{
q[s[i]-'a']=i+'a';
}
zero(cry);
int len=strlen(inter);
if(len==1)
{
printf("%c%c\n",inter[0],q[inter[0]-'a']);
continue;
}
for(i=(len-1)/2+1;inter[i];i++)
cry[i-1-(len-1)/2]=s[inter[i]-'a'];
p[0]=-1;
j=-1;
for(i=1;inter[i];i++)
{
while(j>=0&&inter[j+1]!=inter[i])
j=p[j];
if(inter[j+1]==inter[i])
j++;
p[i]=j;
}
j=-1;
int t;
t=strlen(cry);
//cout<<cry<<endl;
for(i=0;cry[i];i++)
{
while(j>=0&&inter[j+1]!=cry[i])
j=p[j];
if(inter[j+1]==cry[i])
{
j++;
}
cnt[i]=j;
if(j==t)
j=p[j];
}
for(i=0;i<len-cnt[t-1]-1;i++)
printf("%c",inter[i]);
for(i=0;i<len-cnt[t-1]-1;i++)
printf("%c",q[inter[i]-'a']);
printf("\n");
}
return 0;
}