Pagini recente » Cod sursa (job #1367430) | Cod sursa (job #2707857)
///#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
const int SIZE = 2e6+100,
MOD1 = 1e9+7,
MOD2 = 1e9+9,
alpha = 62;
using namespace std;
typedef long long ll;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
char a[SIZE], b[SIZE];
int v[1010], vSize;
int chVal(char ch)
{
if('a'<=ch && ch<='z') return ch-'a';
else if('A'<=ch && ch<='Z') return ch-'A'+26;
else if('0'<=ch && ch<='9') return ch-'0'+52;
return -1;
}
void RK(char s1[], char s2[])
{
int n1=strlen(s1), n2=strlen(s2);
if(n1>n2) {v[vSize++]=0;return;};
ll hsh1=0, hsh2=0, val1=0, val2=0, pam1=1, pam2=1;
for(int i=0; i<n1; i++)
{
hsh1=(hsh1*alpha+chVal(s2[i]))%MOD1;
hsh2=(hsh2*alpha+chVal(s2[i]))%MOD2;
val1=(val1*alpha+chVal(s1[i]))%MOD1;
val2=(val2*alpha+chVal(s1[i]))%MOD2;
if(i)
pam1=(pam1*alpha)%MOD1,
pam2=(pam2*alpha)%MOD2;
}
if(hsh1==val1 && hsh2==val2) v[vSize++]=0;
for(int i=n1; i<n2; i++)
{
hsh1=((hsh1-(chVal(s2[i-n1])*pam1)%MOD1+MOD1)*alpha+chVal(s2[i]))%MOD1;
hsh2=((hsh2-(chVal(s2[i-n1])*pam2)%MOD2+MOD2)*alpha+chVal(s2[i]))%MOD2;
if(hsh1==val1 && hsh2==val2)
{
if(vSize<1000) v[vSize]=i-n1+1;
vSize++;
}
}
}
int main()
{
cin>>a>>b;
RK(a, b);
cout<<vSize<<'\n';
for(int i=0; i<min(1000, vSize); i++)
cout<<v[i]<<' ';
return 0;
}