Pagini recente » Rating Maftei Ioan Alexandru (SlaZzeR) | Statistici Pietrareanu George (Pietrareanu.George) | Cod sursa (job #1121337) | Cod sursa (job #1123884) | Cod sursa (job #2025485)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
int hashFunction(string s){
const long long MOD = (long long) 2e18;
const long long BASE = 123;
long long hashKey = 0;
long long bFactor = BASE;
for (int i = 0; i < (int) s.size(); ++i){
long long aux = bFactor * (long long) s[i];
if (aux > MOD) aux %= MOD;
hashKey = hashKey + aux;
if (hashKey > MOD) hashKey -= MOD;
bFactor = (bFactor * BASE) % MOD;
}
return hashKey;
}
vector <int> stringMatching(string a, string b){
vector <int> pos;
long long bHash = hashFunction(b);
for (int i = 0; i <= (int) a.size() - b.size(); ++i){
if (hashFunction(a.substr(i, b.size())) == bHash){
pos.push_back(i);
}
}
return pos;
}
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
cin >> b >> a;
vector <int> strMatch = stringMatching(a, b);
cout << strMatch.size() << "\n";
for (auto& item : strMatch){
cout << item << " ";
}
return 0;
}