Pagini recente » Cod sursa (job #1581178) | Cod sursa (job #1121859) | Cod sursa (job #2747713) | Cod sursa (job #118016) | Cod sursa (job #236606)
Cod sursa(job #236606)
#include<stdio.h>
#include<string.h>
#define NMAX 2000001
char a[NMAX],b[NMAX];
int n,m,lung=0;
int sol[1001];
long baza[NMAX],hasha=0,hashb=0;
int compara(int j)
{
int i;
for(i=0;i<m;i++)
if(a[i]!=b[j+i])
return 0;
return 1;
}
void RK()
{
int i;
baza[0]=1;
for(i=1;i<m;i++)
baza[i]=(baza[i-1]*32)%100007;
hasha=hashb=0;
for(i=0;i<m;i++)
{
hasha=(hasha+a[i]*baza[m-i-1])%100007;
hashb=(hashb+b[i]*baza[m-i-1])%100007;
}
if(hasha==hashb&&compara(0))sol[++lung]=0;
for(i=1;i<n-m+1;i++)
{
hashb=(hashb-(b[i-1]*baza[m-1])%100007+100007)%100007;
hashb=(hashb*32+b[i+m-1])%100007;
if(hasha==hashb&&compara(i))
if(n>1000&&lung>1000)
lung++;
else
sol[++lung]=i;
}
printf("%d\n",lung);
for(i=1;i<=lung&&i<=1000;i++)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n",a);
scanf("%s",b);
m=strlen(a);
n=strlen(b);
RK();
return 0;
}