1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 const int maxn=1e6+7; 5 string s,t; 6 int n1,n2; 7 bool vis[maxn]; 8 int nxt[maxn],after[maxn],f[maxn],before[maxn]; 9 void process(){ 10 for(int i=1;i<=n2;i++){ 11 int j=nxt[i]; 12 while(j&&t[i+1]!=t[j+1]) j=nxt[j]; 13 nxt[i+1]=(t[i+1]==t[j+1]) ? j+1 : 0; 14 } 15 for(int i=1;i<n1;i++) after[i]=i+1; 16 for(int i=n1;i>=1;i--) before[i]=i-1; 17 } 18 int be(int x){ 19 int cnt=1; 20 while(cnt<=n2){ 21 x=before[x];cnt++; 22 } 23 if(x==0) return 1; 24 else return x; 25 } 26 int main(){ 27 getline(cin,s);n1=s.size(); 28 getline(cin,t);n2=t.size(); 29 for(int i=n1;i>=1;i--) s[i]=s[i-1]; 30 for(int i=n2;i>=1;i--) t[i]=t[i-1]; 31 process(); 32 for (int i=1,k=0;i<=n1;i=after[i]){ 33 if(i==0) break; 34 while(k!=0&&t[k+1]!=s[i]) k=nxt[k]; 35 if (t[k+1]==s[i]) k++; 36 f[i]=k; 37 if (k==n2){ 38 for(int u=i-n2+1;u<=i;u++) vis[u]=true; 39 after[be(i)]=i+1;before[i+1]=be(i); 40 k=f[be(i)]; 41 } 42 } 43 int i=1; 44 while(vis[i]==true) i++; 45 for(;i;i=after[i]) cout<<i<<" "<<s[i]; 46 return 0; 47 }