Pagini recente » Cod sursa (job #1544215) | Cod sursa (job #1714924) | Cod sursa (job #384880) | Cod sursa (job #2307208) | Cod sursa (job #1517006)
#include<cstdio>
#include<cstring>
using namespace std;
char s[4000010];
int z[4000010],sol[1010];
int lit(char ch){
if(ch>='a'&&ch<='z')
return 1;
if(ch>='A'&&ch<='Z')
return 1;
if(ch>='0'&&ch<='9')
return 1;
return 0;
}
int main(){
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int m,n,len,i,l=0,r=0,k,k0,r0,l0,lung,q,p,nr=0;
scanf("%s",&s);
p=strlen(s);
scanf("%s",s+p);
len=strlen(s);
for(i=len;i>=1;i--)
s[i]=s[i-1];
s[0]=NULL;
z[1]=l;
for(k=2;k<=len;k++){
if(k>r){
lung=0;
while(lit(s[k+lung])==1&&s[k+lung]==s[1+lung])
lung++;
z[k]=lung;
l=k;
r=k+lung-1;
}
else{
if(k==1177)
k0++;
l0=1;
r0=r-l+1;
k0=k-l+1;
if(z[k0]<r-k+1)
z[k]=z[k0];
else{
lung=0;
while(lit(s[r+lung])==1&&s[r+lung]==s[z[k0]+lung])
lung++;
q=r+lung;
z[k]=q-k;
r=q-1;
l=k;
}
}
if(z[k]>=p&&k>p){
nr++;
if(nr<=1000)
sol[nr]=k-p-1;
}
}
printf("%d\n",nr);
for(i=1;i<=nr&&i<=1000;i++)
printf("%d ",sol[i]);
return 0;
}