Pagini recente » Cod sursa (job #1901964) | Cod sursa (job #1047744) | Cod sursa (job #1600844) | Cod sursa (job #1092208) | Cod sursa (job #2045007)
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;
#define d 256
ifstream in("strmatch.in");
ofstream out("strmatch.out");
vector <int> rez;
char subsir[2000002],sir[2000002];
int q = 101; /// Numar Prim
int sol;
void rk(char subsir[], char sir[], int q) {
int M = strlen(subsir);
int N = strlen(sir);
int i,j;
int p = 0; // valoare hash pentru subsir
int t = 0; // valoare hash pentru sir
int h = 1;
// valoarea lui h este "pow(d, M-1)%q"
for (i = 0; i < M-1; i++)
h = (h*d)%q;
//Calculam valoarea hash pentru subsir si prima portiune de text
for (i = 0; i < M; i++) {
p = (d*p + subsir[i])%q;
t = (d*t + sir[i])%q;
}
//Punem subsirul peste sir unul cate unul
for (i = 0; i <= N - M; i++) {
//Daca hashurile sunt egale cautam caracter cu caracter
if ( p == t ) {
for (j = 0; j < M; j++) {
if (sir[i+j] != subsir[j])
break;
}
// daca p == t si subsir[0...M-1] = sir[i, i+1, ...i+M-1]
if (j == M) {
sol++;
if(sol <= 1000)
rez.push_back(i);
}
}
// Calculam valoarea hash pentru urmatoarea portiune de text
if ( i < N-M ) {
t = (d*(t - sir[i]*h) + sir[i+M])%q;
//Valoarea lui t poate sa fie < 0 => o facem > 0
if (t < 0)
t = (t + q);
}
}
}
int main(){
in >> subsir >> sir;
rk(subsir, sir, q);
out << sol << '\n';
for(int i=0; i < rez.size(); ++i) out << rez[i] << ' ';
return 0;
}