Pagini recente » Cod sursa (job #418866) | Cod sursa (job #2013493) | Cod sursa (job #194944) | Cod sursa (job #1765583) | Cod sursa (job #2976469)
#include <bits/stdc++.h>
#define MOD1 100021
#define MOD2 100007
#define B 73
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char match[2000001];
int hash11, hash12, nr, b1, b2;
int main()
{
string s1, s2;
fin>>s1>>s2;
int n1=s1.size();
int n2=s2.size();
b1=b2=1;
if(n1>n2)
{
cout<<"0";
return 0;
}
for(int i=0; i<n1; i++)
{
hash11=(hash11*B+s1[i])%MOD1;
hash12=(hash12*B+s1[i])%MOD2;
if(i!=0)
{
b1=(b1*B)%MOD1;
b2=(b2*B)%MOD2;
}
}
int hash21=0;
int hash22=0;
for(int i=0; i<n1; i++)
{
hash21=(hash21*B+s2[i])%MOD1;
hash22=(hash22*B+s2[i])%MOD2;
}
int nr=0;
if(hash11==hash21 && hash12==hash22)
{
match[0]=1;
nr++;
}
for(int i=n1; i<n2; i++)
{
hash21=((hash21-(s2[i-n1]*b1)%MOD1+MOD1)*B+s2[i])%MOD1;
hash22=((hash22-(s2[i-n1]*b2)%MOD2+MOD2)*B+s2[i])%MOD2;
if(hash11==hash21 && hash12==hash22)
{
match[i-n1+1]=1;
nr++;
}
}
fout<<nr<<"\n";
nr=0;
for(int i=0; i<n2 && nr<1000; i++)
{
if(match[i]>0)
{
nr++;
fout<<i<<" ";
}
}
fout<<"\n";
return 0;
}