Pagini recente » Cod sursa (job #2629575) | Cod sursa (job #1176510) | Cod sursa (job #337073) | Cod sursa (job #1235082) | Cod sursa (job #3178828)
#include <fstream>
#include <cstring>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
long long pow1=1,pow2=1;
const long long MOD1=1e9+7;
const long long MOD2=4e9+7;
const long long ct=256;
int poz[1001];
char pattern[2000001],txt[2000001];
int main()
{
cin>>pattern>>txt;
int n=strlen(pattern),m=strlen(txt),i;
long long hashp1=0,hashp2=0;
for(i=0;i<n-1;i++)
{
pow1=pow1*ct%MOD1;
pow2=pow2*ct%MOD2;
hashp1=(hashp1*ct+pattern[i])%MOD1;
hashp2=(hashp2*ct+pattern[i])%MOD2;
}
hashp1=(hashp1*ct+pattern[i])%MOD1;
hashp2=(hashp2*ct+pattern[i])%MOD2;
long long hash1=0,hash2=0;
int rez=0;
for(i=0;i<n&&i<m;i++)
{
hash1=(hash1*ct+txt[i])%MOD1;
hash2=(hash2*ct+txt[i])%MOD2;
}
i--;
while(i<m-1)
{
if(hash1==hashp1&&hash2==hashp2)
{
rez++;
if(rez<=1000)
poz[rez]=i-n+1;
}
i++;
hash1=((MOD1+hash1-pow1*txt[i-n]%MOD1)*ct+txt[i])%MOD1;
hash2=((MOD2+hash2-pow2*txt[i-n]%MOD2)*ct+txt[i])%MOD2;
}
if(hash1==hashp1&&hash2==hashp2)
{
rez++;
if(rez<=1000)
poz[rez]=i-n+1;
}
cout<<rez<<'\n';
rez=min(rez,1000);
for(i=1;i<=rez;i++)
cout<<poz[i]<<" ";
return 0;
}