Pagini recente » Cod sursa (job #1521202) | Cod sursa (job #2896781) | Cod sursa (job #2901996) | Cod sursa (job #3141832) | Cod sursa (job #2169110)
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int h1, h2, v[2000000];
int create_hash1(char pat[], int &j){
int i, n = strlen(pat);
for(i = 0; i < n; i++){
j = j + (pat[i] - 'a' + 1) * powl(3, i);
}
return j;
}
int create_hash2(char pat[], int &j){
int i, n = strlen(pat);
for(i = 0; i < n; i++){
j = j + (pat[i] - 'a' + 1) * powl(5, i);
}
return j;
}
int rabin_karp(char text[], char pat[], int h1, int h2, int v[]){
int i, j, k = 0, c = 1, m = strlen(text), n = strlen(pat), g1, g2;
char p[n];
for(i = 0; i < m; i++){
g1 = 0; g2 = 0;
for(j = 0; j < n; j++)
p[j] = text[i + j];
create_hash1(p, g1);
create_hash2(p, g2);
if(h1 == g1 && h2 == g2){
v[k] = i;
k++;
}
}
return k;
}
int main()
{
char text[1000000], pat[1000000];
fin >> pat >> text;
int da, i;
h1 = create_hash1(pat, h1);
h2 = create_hash2(pat, h2);
da = rabin_karp(text, pat, h1, h2, v);
fout << da << endl;
for(i = 0; i < da; i++)
fout << v[i] << " ";
fin.close();
fout.close();
return 0;
}