Pagini recente » Cod sursa (job #2933130) | Cod sursa (job #2366737) | Cod sursa (job #2897547) | Cod sursa (job #2972267) | Cod sursa (job #2344143)
#include <fstream>
#include <cstring>
#include <cmath>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int h, v[2000000];
int create_hash(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 rabin_karp(char text[], char pat[], int h, int v[]){
int i, j, k = 0, c = 1, m = strlen(text), n = strlen(pat), g;
char p[n];
for(i = 0; i < m; i++){
g = 0;
for(j = 0; j < n; j++)
p[j] = text[i + j];
create_hash(p, g);
if(h == g){
c = 1;
for(j = 0; j < n; j++)
if(pat[j] != p[j]){
c = 0;
break;
}
if(c == 1){
v[k] = i;
k++;
}
}
}
return k;
}
int main()
{
char text[1000000], pat[1000000];
fin >> pat >> text;
int da, i;
h = create_hash(pat, h);
da = rabin_karp(text, pat, h, v);
fout << da << '\n';
for(i = 0; i < da; i++)
fout << v[i] << " ";
fin.close();
fout.close();
return 0;
}