Pagini recente » Cod sursa (job #2917068) | Cod sursa (job #1913052) | Cod sursa (job #1349469) | Cod sursa (job #3040153) | Cod sursa (job #2284504)
#include <fstream>
#include <cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char p[2000000], t[2000000];
long long int n, m, nrpoz;
int poz[2000000];
struct Hash
{
long long int n, m, power, hash1;
void init(char *s,long long int len)
{
power=1, hash1=0;
for(long long int i=len-1; i>=0; i--)
{
hash1=(hash1+(power*s[i])%m)%m;
if(i)
power=(power*n)%m;
}
}
void roll(char toRemove, char toAdd)
{
hash1=(((hash1-(toRemove*power)%m+m)*n)%m+toAdd)%m;
}
};
int main()
{
in>>p>>t;
n=strlen(p);
m=strlen(t);
Hash pHash{31, 40099}, tHash{31, 40099};
Hash pHash2{53, 319993}, tHash2{53, 319993};
pHash.init(p, n);
tHash.init(t, n);
pHash2.init(p, n);
tHash2.init(t, n);
if(pHash.hash1 == tHash.hash1 && pHash2.hash1==tHash2.hash1)
poz[++nrpoz]=0;
for(long long int i=n; i<m; i++)
{
tHash.roll(t[i-n], t[i]);
tHash2.roll(t[i-n], t[i]);
if(pHash.hash1 == tHash.hash1 && pHash2.hash1==tHash2.hash1)
{
if(nrpoz<=1000)
poz[++nrpoz]=(i-n+1);
else
nrpoz++;
}
}
out<<nrpoz<<endl;
if(nrpoz>1000)
nrpoz=1000;
for(int i=1; i<=nrpoz; i++)
out<<poz[i]<<' ';
return 0;
}