Pagini recente » Cod sursa (job #2109437) | Cod sursa (job #271319) | Cod sursa (job #2781251) | Cod sursa (job #2279815) | Cod sursa (job #2707891)
///#include <iostream>
#include <fstream>
#include <cstring>
#include <cmath>
const int SIZE = 2e6+100,
MOD1 = 1e9+9,
MOD2 = 666013,
alpha = 62;
using namespace std;
typedef long long ll;
fstream cin("strmatch.in");
ofstream cout("strmatch.out");
int charVal(char x)
{
if('0'<=x && x<='9') return x-'0';
if('a'<=x && x<='z') return x-'a'+10;
if('A'<=x && x<='Z') return x-'A'+36;
return -1;
}
int v[1010], vSize;
void RK(char s1[], char s2[])
{
int n1=strlen(s1), n2=strlen(s2);
if(n1>n2) return;
ll hsh1=0, hsh2=0, val1=0, val2=0, p1=1, p2=1;
for(int i=0; i<n1; i++)
{
if(i) p1=(p1*alpha)%MOD1, p2=(p2*alpha)%MOD2;
hsh1=(hsh1*alpha+charVal(s2[i]))%MOD1;
hsh2=(hsh2*alpha+charVal(s2[i]))%MOD2;
val1=(val1*alpha+charVal(s1[i]))%MOD1;
val2=(val2*alpha+charVal(s1[i]))%MOD2;
}
if(hsh1==val1 && hsh2==val2) v[vSize++]=0;
for(int i=n1; i<n2; i++)
{
hsh1=(((hsh1-(charVal(s2[i-n1])*p1)%MOD1+MOD1)%MOD1)*alpha+charVal(s2[i]))%MOD1;
hsh2=(((hsh2-(charVal(s2[i-n1])*p2)%MOD2+MOD2)%MOD2)*alpha+charVal(s2[i]))%MOD2;
if(hsh1==val1 && hsh2==val2)
{
if(vSize<1000) v[vSize]=i-n1+1;
vSize++;
}
}
}
char a[SIZE], b[SIZE];
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;
}