Pagini recente » Cod sursa (job #182897) | Cod sursa (job #3214722) | Cod sursa (job #1076830) | Cod sursa (job #1538205) | Cod sursa (job #2066899)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 2000005
#define mod1 9833
#define mod2 9973
#define baza 256
using namespace std;
char a[N], b[N];
int sol[N], n, m;
void hasis()
{
int p1=1, p2=1, hA1=a[0]%mod1, hA2=a[0]%mod2, h1=b[0]%mod1, h2=b[0]%mod2;
for(int i=1;i<n;i++)
{
hA1=(hA1*baza+a[i])%mod1;
hA2=(hA2*baza+a[i])%mod2;
h1=(h1*baza+b[i])%mod1;
h2=(h2*baza+b[i])%mod2;
p1=(p1*baza)%mod1;
p2=(p2*baza)%mod2;
}
for(int i=n;i<=m;i++)
{
if(h1==hA1 && h2==hA2)
sol[++sol[0]]=i-n;
h1=(((h1-(b[i-n]*p1)%mod1+mod1)*baza%mod1)+b[i])%mod1;
h2=(((h2-(b[i-n]*p2)%mod2+mod2)*baza%mod2)+b[i])%mod2;
}
}
void afisare()
{
printf("%d\n", sol[0]);
int nr=min(sol[0], 1000);
for(int i=1;i<=nr;i++)
printf("%d ", sol[i]);
}
int main()
{
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
fgets(a, N, stdin);
fgets(b, N, stdin);
n=strlen(a)-1;
m=strlen(b)-1;
hasis();
afisare();
return 0;
}