Pagini recente » Cod sursa (job #1467145) | Cod sursa (job #886714) | Cod sursa (job #1774189) | Cod sursa (job #2332887) | Cod sursa (job #1981737)
#include <stdio.h>
#include <vector>
#include <cstring>
#define maxn 2000000+5
#define mod1 140009
#define mod2 156007
using namespace std;
vector <int> v;
char a[maxn],c[maxn];
int hashc1,hashc2,hasha1,hasha2,p1=1,p2=1,P=101,n,m,k;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s""%s",c+1,a+1);
n=strlen(a+1);
m=strlen(c+1);
for(int i=1;i<=m;i++)
{
hashc1=(hashc1*P+c[i])%mod1;
hashc2=(hashc2*P+c[i])%mod2;
if(i!=1)
p1=(p1*P)%mod1,p2=(p2*P)%mod2;
}
for(int i=1;i<=m;i++)
{
hasha1=(hasha1*P+a[i])%mod1;
hasha2=(hasha2*P+a[i])%mod2;
}
if(hasha1==hashc1&&hasha2==hashc2)
k++,v.push_back(0);
for(int i=m+1;i<=n;i++)
{
hasha1=(((hasha1-(a[i-m]*p1)%mod1+mod1)%mod1)*P+a[i])%mod1;
hasha2=(((hasha2-(a[i-m]*p2)%mod2+mod2)%mod2)*P+a[i])%mod2;
if(hasha1==hashc1&&hasha2==hashc2)
k++,v.push_back(i-m);
}
printf("%d\n",k);
for(int i=0;i<k&i<=1000;i++)
printf("%d ",v[i]);
return 0;
}