Pagini recente » Cod sursa (job #2201625) | Rating Ionut Birescu (IonutB56) | Cod sursa (job #1610947)
#include <fstream>
#include <cstring>
#define mod1 100007
#define mod2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[200005],b[200005];
char match[200005];
int na,nb;
int hasha1, hasha2 ,p1, p2,p,i;
int main()
{
fin.getline(a,200005);
fin.getline(b,200005);
p1=p2=1;
na=strlen(a);
nb=strlen(b);
for(i=0; i<na; i++)
{
hasha1=(hasha1*p +a[i])% mod1;
hasha2=(hasha2*p +a[i])% mod2;
if(i!=0)
p1=(p1*p) %mod1;
p2=(p2*p) %mod2;
}
if(na>nb)
{
fout<<"0";
return 0;
}
int hash1=0;
int hash2=0;
for (i=0; i<na; i++)
{
hash1 = (hash1 * p + b[i]) % mod1;
hash2 = (hash2 * p + b[i]) % mod2;
}
int nr=0;
if (hash1 == hasha1 && hash2 == hasha2)
{
match[0]=1;
++nr;
}
for (i=na; i<nb; i++)
{
hash1 = ((hash1-(b[i-na] * p1) % mod1 + mod1) * p + b[i]) % mod1;
hash2 = ((hash2-(b[i-na] * p2) % mod2 + mod2) * p + b[i]) % mod2;
if (hash1 == hasha1 && hash2 == hasha2)
match[i-na+1]=1, nr++;
}
fout<<nr<<'\n';
nr=0;
for(i=0; i<nb && nr<1000; i++)
if(match[i]!=0)
{
fout<<i<<" ";
nr++;
}
return 0;
}