Fix a Weird Speaker

Mr.Colorful recently purchased a smart bluetooth speaker. He was quite satisfied with the speaker, except that something may went wrong when the speaker responds to him.

One day, Mr.Colorful found that the speaker produced a weird sentence, but he could not remember what exactly it said.

Based on impressions, Mr.Coloful was sure that the speaker wanted to say a sentence $T$ $(1 \le |T| \le 2\times 10^6)$ , a string consisting of only lower case letters.

He believed that the sentence he heard sounded weird because a nonempty subinterval of $T$ must have been repeated immediately after its occurrence.

Formally speaking, a string $W$ is said to be a weird sentence originated from $T$ , if and only if there exists two integers $i, j$ $(1 \le i \le j \le |T|)$ , such that $W = T_{1 \dots i - 1} + T_{i \dots j} + T_{i \dots j} + T_{j + 1 \dots |T|}$ ,

where "+" means string concatenation and $T_{l \dots r}$ means the substring of $T$ located at $l \dots r$ .

Note that $T_{i \dots j}$ denotes an empty string when $i > j$ .

Mr.Colorful opened the log of his speaker. The log is also a string $S$ $(1 \le |S| \le 2\times 10^6)$ consisting of only lower case letters.

Given $T$ , help Mr.Colorful to find the longest substring of $S$ such that it is a weird sentence originated from $T$ .

If there are multiple such strings, please output the string with the leftmost start position.

If in the log $S$ there exists a weird sentence originated from $T$ , please output two integers $l$ and $r$ seperated by a space, denoting the location of the longest weird sentence (the string is 1-indexed). You need to ensure that $l$ is minimized.

Otherwise, output $-1$ .

#include<cstdio> #include<algorithm> #include<cstring> #define fo(i,x,y) for(int i=x;i<=y;i++) #define fr(i,x,y) for(int i=x;i>=y;i--) using namespace std; const int N=2e6+2; int f[N],g[N],w[N],n,m; char a[N],b[N]; int main(){ scanf("%s",b+1); m=strlen(b+1); scanf("%s",a+1); n=strlen(a+1); int j=0; f[1]=0; fo(i,2,n){ while (j!=0 && a[j+1]!=a[i]) j=f[j]; if (a[j+1]==a[i]) f[i]=j+1,j+=1; } j=0; fo(i,1,m){ while (j!=0 && a[j+1]!=b[i]) j=f[j]; if (a[j+1]==b[i]) j+=1,g[i]=j; } f[n]=n+1; j=n+1; fr(i,n-1,1){ while (j!=n+1 && a[j-1]!=a[i]) j=f[j]; if (a[j-1]==a[i]) f[i]=j-1,j-=1; else f[i]=n+1,j=n+1; } j=n+1; fr(i,m,1){ while (j!=n+1 && a[j-1]!=b[i]) j=f[j]; if (a[j-1]==b[i]) w[i]=j-1,j-=1; else w[i]=n+1,j=n+1; } int ans=0,k=0; fo(i,1,m-1){ j=g[i]+n+1-w[i+1]; //printf("%d %d\n",i,w[i]); if (j>n and j>ans){ ans=j; k=i-g[i]+1; } } if (k==0) printf("-1"); else printf("%d %d",k,k+ans-1); }

详情