Pagini recente » Cod sursa (job #436623) | Cod sursa (job #909521) | Cod sursa (job #2480441) | Cod sursa (job #2922566) | Cod sursa (job #2064555)
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 2000005
#define mod 101
#define baza 256
using namespace std;
char a[N], b[N];
int sol[N], n, m;
int comp(int k)
{
for(int i=0;i<n;i++)
{
if(a[i]!=b[k])
return 0;
k++;
}
return k;
}
void hasis()
{
int p=1, hA=a[0]%mod, h=b[0]%mod;
for(int i=1;i<n;i++)
{
hA=(hA*baza+a[i])%mod;
h=(h*baza+b[i])%mod;
p=(p*baza)%mod;
}
for(int i=n;i<m;i++)
{
if(h==hA && comp(i-n)==i)
sol[++sol[0]]=i-n;
h=(((h-(b[i-n]*p)%mod+mod)*baza%mod)+b[i])%mod;
}
if(h==hA && comp(m-n)==m)
sol[++sol[0]]=m-n;
}
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;
}