Pagini recente » Cod sursa (job #1023739) | Cod sursa (job #2661382) | Cod sursa (job #1948315) | Cod sursa (job #2405278) | Cod sursa (job #1328174)
// 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 73
char A[MAX], B[MAX];
int NA, NB;
int hashA1, hashA2, P1, P2, sol[1001];
int main()
{
int P1=1, P2=1;
fin.getline(A, MAX); NA=strlen(A);
fin.getline(B, MAX); NB=strlen(B);
int hash1=0, hash2=0;
if(NA>NB) { fout<<"0\n"; return 0;}
for(int i=0; i<NA; i++){
hashA1=(hashA1*base1 + A[i])%MOD1;
hashA2=(hashA2*base1 + A[i])%MOD2;
hash1=(hash1*base1 + B[i])%MOD1;
hash2=(hash2*base1 + B[i])%MOD2;
if(i!=0) P1*=base1,
P2*=base1;
}
if(hashA1==hash1 && hashA2==hash2)
sol[++sol[0]]=1;
for(int i=0; i<NB-NA; i++){
hash1=((hash1-(P1*B[i])%MOD1+MOD1)*base1+B[NA+i])%MOD1;
hash2=((hash2-(P2*B[i])%MOD2+MOD2)*base1+B[NA+i])%MOD2;
if(hash1==hashA1 && hash2==hashA2){
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;
}