Pagini recente » Cod sursa (job #288137) | Cod sursa (job #1159903) | Cod sursa (job #255463) | Cod sursa (job #972310) | Cod sursa (job #1328173)
// 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);
if(n>m) { fout<<"00\n"; return 0;}
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;
for(int i=0; i<m-n; i++){
s_hash1=((s_hash1-(P1*M[i])%MOD1+MOD1)*base1+M[n+i])%MOD1;
s_hash2=((s_hash2-(P2*M[i])%MOD2+MOD2)*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;
}