Pagini recente » Cod sursa (job #1498746) | Cod sursa (job #1788744) | Cod sursa (job #6039) | Cod sursa (job #279039) | Cod sursa (job #2574718)
#include <bits/stdc++.h>
#define MODULO1 100019
#define MODULO2 100021
#define DMAX 2000007
#define putere 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int hash1a,hash2a,hash1b,hash2b;
char a[DMAX],b[DMAX];
vector<int> v;
int put1,put2;
int main()
{int lg1,i,lg2;
fin.getline(a,DMAX);
fin.getline(b,DMAX);
lg1=strlen(a);
lg2=strlen(b);
put1=put2=1;
if(lg1>lg2)
{fout<<0;return 0;}
for(i=0;i<lg1;i++)
{
hash1a=(hash1a*putere+a[i])%MODULO1;
hash2a=(hash2a*putere+a[i])%MODULO2;
hash1b=(hash1b*putere+b[i])%MODULO1;
hash2b=(hash2b*putere+b[i])%MODULO2;
if(i!=0)
put1=(put1*putere)%MODULO1,put2=(put2*putere)%MODULO2;
}
if(hash1a==hash1b&&hash2a==hash2b)
v.push_back(0);
for(i=lg1;i<lg2;i++)
{
hash1b=((hash1b-(b[i-lg1]*put1)%MODULO1+MODULO1)*putere+b[i])%MODULO1;
hash2b=((hash2b-(b[i-lg1]*put2)%MODULO2+MODULO2)*putere+b[i])%MODULO2;
if(hash1a==hash1b&&hash2a==hash2b)
v.push_back(i-lg1+1);
}
fout<<v.size()<<'\n';
for(i=0;i<v.size()&&i<1000;i++)
fout<<v[i]<<' ';
return 0;
}