Pagini recente » Cod sursa (job #311661) | Cod sursa (job #892191) | Cod sursa (job #881593) | Cod sursa (job #1315061) | Cod sursa (job #1328169)
// Rabin Karp (2 bases)
#include <fstream>
#include <string.h>
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 pow(int n, int exp){
int result=1;
for(int i=1; i<=exp; i++)
result*=n;
return result;
}
int main()
{
fin.getline(N, MAX); n=strlen(N);
fin.getline(M, MAX); m=strlen(M);
for(int i=0; i<n; i++)
p_hash1+=N[i]*pow(base1, n-(i+1))%MOD1,
p_hash2+=N[i]*pow(base2, n-(i+1))%MOD2;
for(int i=0; i<n; i++)
s_hash1+=M[i]*pow(base1, n-(i+1))%MOD1,
s_hash2+=M[i]*pow(base2, n-(i+1))%MOD2;
if(p_hash1==s_hash1 && p_hash2==s_hash2)
sol[++sol[0]]=1;
else {
for(int i=0; i<m-n; i++){
s_hash1=((s_hash1-M[i]*pow(base1, n-1))*base1+M[n+i])%MOD1,
s_hash2=((s_hash2-M[i]*pow(base2, n-1))*base2+M[n+i])%MOD2;
if(s_hash1==p_hash1 && p_hash2==s_hash2)
{
sol[0]++;
if(sol[0]<=1000) sol[sol[0]]=i+1;
}
}
}
fout<<sol[0]<<"\n";
for(int i=1; i<=sol[0]; i++)
fout<<sol[i]<<" ";
fin.close();
fout.close();
return 0;
}