Pagini recente » Cod sursa (job #125994) | Cod sursa (job #801557) | Cod sursa (job #2745922) | Cod sursa (job #1499662) | Cod sursa (job #1739723)
#include <fstream>
#include <cstring>
using namespace std;
const int p=73, MOD1=100007, MOD2=100021, NMAX=2000001;
int hashs1, hashs2, p1, p2, n1, n2;
char s1[NMAX], s2[NMAX], match[NMAX];
int main()
{
ifstream in("strmatch.in");
ofstream out("strmatch.out");
in>>s1>>s2;
n1=strlen(s1);
n2=strlen(s2);
p1=p2=1;
hashs1=hashs2=0;
for(int i=0; i<n1; i++)
{
hashs1=(hashs1*p+s1[i])%MOD1;
hashs2=(hashs2*p+s1[i])%MOD2;
if(i!=0)
{
p1=(p1*p)%MOD1;
p2=(p2*p)%MOD2;
}
}
if(n1>n2)
{
out<<0<<'\n';
return 0;
}
int hash1=0, hash2=0;
for(int i=0; i<n1; i++)
{
hash1=(hash1*p+s2[i])%MOD1;
hash2=(hash2*p+s2[i])%MOD2;
}
int nr=0;
if(hash1==hashs1 && hash2==hashs2)
{
match[0]=1;
nr++;
}
for(int i=n1; i<n2; i++)
{
hash1=((hash1-(s2[i-n1]*p1)%MOD1+MOD1)*p+s2[i])%MOD1;
hash2=((hash2-(s2[i-n1]*p2)%MOD2+MOD2)*p+s2[i])%MOD2;
if(hash1==hashs1 && hash2==hashs2)
{
match[i-n1+1]=1;
nr++;
}
}
out<<nr<<'\n';
nr=0;
for(int i=0; i<n2 && nr<1000; i++)
if(match[i])
{
nr++;
out<<i<<' ';
}
out<<'\n';
return 0;
}