Pagini recente » Cod sursa (job #915577) | Cod sursa (job #539051) | Cod sursa (job #2575104) | Cod sursa (job #2317228) | Cod sursa (job #2419137)
#include <iostream>
#include <fstream>
#include <cstring>
#define MOD 1000000007
#define LMAX 2000003
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str1;
string str2;
long long k, h1, h2,b, r, n,m,i;
int rs[LMAX];
int main()
{
fin>>str1>>str2;
n = str1.size();
m = str2.size();
b=1;
for(i=n-1;i>=0; i--)
{
k=(k+(str1[i])*b%MOD+MOD)%MOD;
h1+=((str2[i])*b%MOD+MOD)%MOD;
b=(b*31+MOD)%MOD;
}
if(k==h1)
rs[r++]=0;
for(i=n; i<m; i++)
{
//h2=((h1*31)%MOD-((str2[st-1]-'A')*pow(31, lp))%MOD+str2[dr]-'A')%MOD;
h1=(((h1*31+MOD)%MOD-((str2[i-n])*b+MOD)%MOD+MOD)%MOD+str2[i]+MOD)%MOD;
h1=(h1+MOD)%MOD;
if(k==h1)
rs[r++]=i-n+1;
}
int rr = min(r,1LL*1000);
fout<<r<<'\n';
for(i=0; i<rr; i++)
fout<<rs[i]<<' ';
return 0;
}