Pagini recente » Cod sursa (job #2677105) | Cod sursa (job #2783082) | Cod sursa (job #1375069) | Cod sursa (job #390222) | Cod sursa (job #2063373)
#include <iostream>
#include <cstdio>
#include <cstring>
#define N 2000005
#define mod 101
#define baza 256
using namespace std;
char a[N], b[N];
int ap[N], n, m, l;
void hasis()
{
int p=1, hA=a[1], h=b[1];
for(int i=2;i<=n;i++)
{
hA=(hA*baza+a[i])%mod;
if(i!=1)
p=(p*baza)%mod;
}
for(int i=2;i<=n;i++)
h=(h*baza+b[i])%mod;
for(int i=n+1;i<=m;i++)
{
h=((h-(b[i-n]*p)%mod+mod)*baza+b[i])%mod;
if(h==hA)
ap[i-n+1]=1, l++;
}
}
void afisare()
{
printf("%d\n", l);
l=0;
for(int i=0;i<m && l<1000;i++)
if(ap[i])
{
l++;
printf("%d ", i-1);
}
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a+1, N, stdin);
fgets(b+1, N, stdin);
n=strlen(a+1)-1;
m=strlen(b+1)-1;
hasis();
afisare();
return 0;
}