Pagini recente » Cod sursa (job #1027818) | Cod sursa (job #2030597) | Cod sursa (job #1099742) | Cod sursa (job #1208318) | Cod sursa (job #2025479)
#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 < s.size(); ++i){
hashKey = (hashKey + (bFactor * 1LL * (long long)s[i]) % MOD) % 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 <= 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;
}