Pagini recente » Cod sursa (job #2073032) | Cod sursa (job #2425888) | Cod sursa (job #2377798) | Cod sursa (job #602117) | Cod sursa (job #1696618)
#include<cstdio>
#include<cstring>
#include<algorithm>
void lol(){
int x=0;
x++;
}
using namespace std;
const int L=2000000;
char s1[L+1];
char s2[2*L+1];
int z[2*L+1];
int ans[L+1];
int l,r,n1,n2,res;
void set_z(){
for(int i=1;i<n2+n1;i++){
if(i==4)
lol();
if(r<i){
int j=0;
while(s2[j]==s2[i+j]&&j<n1)
j++;
j--;
if(j>=0){
r=j+i;
l=i;
z[i]=r-l+1;
}
}
else{
int ii=z[l]-(r-i+1);
if(z[ii]){
if(ii+z[ii]-1<z[l]-1){
z[i]=z[ii];
l=i;
r=i+z[i]-1;
}
else{
int j=r-i+1;
while(s2[j]==s2[i+j]&&j<n1)
j++;
j--;
r=j+i;
l=i;
z[i]=r-l+1;
}
}
}
}
}
void z_algo(){
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
gets(s2);
gets(s1);
n1=strlen(s1);
n2=strlen(s2);
for(int i=0;i<n1;i++)
s2[n2+i]=s1[i];
set_z();
for(int i=n2;i<n2+n1;i++)
if(z[i]>=n2)
ans[++res]=i-n2;
printf("%d\n",res);
for(int i=1;i<=min(res,1000);i++)
printf("%d ",ans[i]);
return 0;
}