Pagini recente » Cod sursa (job #2061468) | Cod sursa (job #331236) | Cod sursa (job #1757688) | Cod sursa (job #1870278) | Cod sursa (job #2284482)
#include <iostream>
#include <cstring>
#include <fstream>
struct Hash {
int n,m,power,hash;
void init(char *s, int len)
{
power=1,hash=1;
for (int i=len-1;i>=0;i--)
{
hash=(hash + 1LL * power * s[i])%m;
if (i)
power=(power*n)%m;
}
}
void roll(char toRemove , char toAdd)
{
hash=(((hash - toRemove * power + m)*n)%m + toAdd)%m;
}
};
using namespace std;
ifstream f ("date.in");
ofstream g ("date.out");
int main()
{
char p[100], t[100];
int n,m,nr=0,k=0,v[100];
f>>p>>t;
n=strlen(p),m=strlen(t);
Hash pHash{3,666013}, tHash{3,666013};
pHash.init(p,n);
tHash.init(t,n);
if (pHash.hash==tHash.hash)
{
cout<<" ";
nr++;
}
for (int i=n;i<m;i++)
{
tHash.roll(t[i-n],t[i]);
if (pHash.hash==tHash.hash)
{
v[k++]=i-n+1;
nr++;
}
}
cout<<nr<<"\n";
for (int i=0;i<k;i++)
cout<<v[i]<<" ";
return 0;
}