#include<bits/stdc++.h>
using namespace std;
#define maxn 500005
int p[maxn];
char s[maxn],s_new[maxn],ch[
2];
int start;
int init(){
int len=
strlen(s);
int j=
2;
s_new[0]=
'$',s_new[
1]=
'#';
for(
int i=
0;i<len;i++
){
s_new[j++]=
s[i];
s_new[j++]=
'#';
}
s_new[j]=
0;
return j;
}
int manacher(){
int len=
init();
int mx=
0,id,res=
0;
start=
0;
for(
int i=
0;i<len;i++
){
if(mx>i)p[i]=min(p[id*
2-i],mx-
i);
else p[i]=
1;
while(s_new[i-p[i]]==s_new[i+p[i]])p[i]++
;
if(mx<i+
p[i])
mx=i+p[i],id=
i;
if(res<p[i]-
1)
res=p[i]-
1,start=(i-p[i]+
2)/
2-
1;
}
return res;
}
int main(){
while(scanf(
"%s%s",ch,s)!=
EOF){
memset(p,0,
sizeof p);
int res=
manacher();
if(res<=
1){
puts("No solution!");
continue;
}
cout<<start<<
" "<<start+res-
1<<
'\n';
for(
int i=start;i<start+res;i++
){
if(s[i]-ch[
0]>=
0)cout<<(
char)(s[i]-ch[
0]+
'a');
else cout<<(
char)(s[i]-ch[
0]+
26+
'a');
}
puts("");
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10784774.html
