Pagini recente » Istoria paginii runda/343242354534/clasament | Cod sursa (job #2686823) | Cod sursa (job #2847313) | Cod sursa (job #1573001) | Cod sursa (job #2675995)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//RABIN-KARP
//PRESUPUNEM CA HASH-UL ESTE SUMA CODURILOR ASCII ALE CARACTERELOR
//CA SA FIE MAI SIMPLU DE INTELES DE MINE
string A,B;
int hash_table[100000];
vector <int> positions;
int main(){
fin >> A >> B;
//cout << A <<" " << B << endl;
unsigned int n = A.size();
unsigned int m = B.size();
//calculate hash of A string
int hash_A = 0,j=0;
for(int i = 0; i < n; i++)
hash_A += int(A[i]);
//cout << hash_A << endl;
hash_table[0] = int(B[0]);
for(int i = 1; i < m-n+1; i++){
hash_table[i] = int(B[i]) + hash_table[i-1];
//if current window hash is equal with hash(A)
//cout << "window-ul " << i << " "<<i-n+1<<" "<< hash_table[i] - hash_table[i-n+1] << "\n";
if( i >= n){
if(hash_table[i] - hash_table[i-n] == hash_A){
for(j = 0; j < n; j++)
if(B[i-n+1+j] != A[j])
break;
if(j == n)//daca a parcurs tot for-ull fara intrerupere chiar matching
positions.push_back(i-n+1);
}
}
}
fout << positions.size() << "\n";
for(int i = 0; i < positions.size(); ++i)
fout << positions[i] << " ";
//for(int i = 0; i < m; i++)
// cout << hash_table[i] << " ";
fin.close();
fout.close();
return 0;
}