Pagini recente » Cod sursa (job #527254) | Cod sursa (job #547144) | Cod sursa (job #217790) | Cod sursa (job #3213505) | Cod sursa (job #1328172)
// Rabin Karp (2 bases)
#include <fstream>
#include <string.h>
#include <algorithm>
using namespace std;
fstream fin("strmatch.in", ios::in);
fstream fout("strmatch.out", ios::out);
#define MAX 2000005
#define MOD1 100007
#define MOD2 100021
#define base1 27
#define base2 29
char N[MAX], M[MAX], sub[MAX];
int n, m;
int p_hash1, p_hash2, s_hash1, s_hash2, sol[MAX];
int main()
{
int P1=1, P2=1;
fin.getline(N, MAX); n=strlen(N);
fin.getline(M, MAX); m=strlen(M);
for(int i=0; i<n; i++){
p_hash1=(p_hash1*base1 + N[i])%MOD1;
p_hash2=(p_hash2*base2 + N[i])%MOD2;
s_hash1=(s_hash1*base1 + M[i])%MOD1;
s_hash2=(s_hash2*base2 + M[i])%MOD2;
if(i!=0) P1*=base1,
P2*=base2;
}
if(p_hash1==s_hash1 && p_hash2==s_hash2)
sol[++sol[0]]=1;
if(n>m) { fout<<"0\n"; return 0;}
for(int i=0; i<m-n; i++){
s_hash1=((s_hash1-P1*M[i])*base1+M[n+i])%MOD1;
s_hash2=((s_hash2-P2*M[i])*base2+M[n+i])%MOD2;
if(s_hash1==p_hash1 && s_hash2==p_hash2){
sol[0]++;
if(sol[0]<=1000) sol[sol[0]]=i+1;
}
}
fout<<sol[0]<<"\n";
for(int i=1; i<=min(1000, sol[0]); i++)
fout<<sol[i]<<" ";
fin.close();
fout.close();
return 0;
}