Pagini recente » Cod sursa (job #2959632) | Cod sursa (job #1443946) | Cod sursa (job #2569964) | Statistici Gheoace Mircea (MIrcea_Gheoace) | Cod sursa (job #3192969)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int N=2e6;
const int MOD=1e9+2727;
char a[N],b[N];
int hashh[N];
int v[1001];
int cif(char ch)
{
if('a'<=ch && ch<='z')
return ch-'a'+1;
if('A'<=ch && ch<='a')
return ch-'A'+27;
return ch-'0'+53;
}
int main()
{
int cod=0,baza=63,asize,bsize,put,i,cnt,val;
fin>>a>>b;
asize=strlen(a);
bsize=strlen(b);
put=1;
for(i=0;i<asize;i++){
cod=(1LL*cod*baza+cif(a[i]))%MOD;
put=(1LL*put*baza)%MOD;
}
hashh[0]=cif(b[0]);
for(i=1;i<bsize;i++)
hashh[i]=(1LL*hashh[i-1]*baza+cif(b[i]))%MOD;
cnt=0;
if(hashh[asize-1]==cod)
{
cnt++;
v[cnt]=0;
}
for(i=asize;i<bsize && cnt<1000;i++)
{
val=hashh[i]-(1LL*hashh[i-asize]*put)%MOD;
if(val<0)
val+=MOD;
if(val==cod)
{
cnt++;
v[cnt]=i-asize+1;
}
}
fout<<cnt<<'\n';
for(i=1;i<=cnt;i++)
fout<<v[i]<<" ";
return 0;
}