Pagini recente » Cod sursa (job #1139061) | Cod sursa (job #378949) | Cod sursa (job #1067633) | Cod sursa (job #1009641) | Cod sursa (job #2172307)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000005],b[2000005];
int v[2000005],sol;
int p;
int hashf(char str[],int l)
{
int resulthash=0;
p=1;
for(int i=0;i<l;i++)
{
resulthash=((resulthash*256)%47+str[i])%47;
if(i!=0)
p=(p*256)%47;
}
return resulthash;
}
int nexthash(int prev,int next,int curhash)
{
return (((curhash-(p*prev)%47)*256)%47+next)%47;
}
void dummy(int start,int l)
{
for(int i=0,j=start;i<l;i++,j++)
{
if(a[i]!=b[j])
return;
}
v[++sol]=start;
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s\n%s",a,b);
const int lb=strlen(b),la=strlen(a);
const int searchfor=hashf(a,la);
int curhash=hashf(b,la);
if(searchfor==curhash)
dummy(0,la);
for(int i=la;i<lb;i++)
{
curhash=nexthash(b[i-la],b[i],curhash);
if(searchfor==curhash)
dummy(i-la+1,la);
}
printf("%d\n",sol);
for(int i=1;i<=sol;i++)
printf("%d ",v[i]);
return 0;
}