Pagini recente » Profil ziende | Cod sursa (job #1565381) | Cod sursa (job #1128218) | Cod sursa (job #2427436) | Cod sursa (job #2025518)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
const long long MOD = (long long) 2e18;
const long long BASE = 123;
long long fastExp(long long n, int exp){
switch(exp){
case 0 : return 1;
default : return (exp % 2 == 0) ? fastExp((n * n) % MOD, exp >> 1) : (n * fastExp(n, --exp)) % MOD;
}
}
int hashFunction(string s){
long long hashKey = 0;
for (int i = 0; i < (int) s.size(); ++i){
hashKey = (hashKey + fastExp(BASE, s.size() - 1 - i) * (long long) s[i]) % MOD;
}
return hashKey;
}
vector <int> stringMatching(string a, string b){
if (b.size() > a.size()){
return {};
}
vector <int> pos;
long long bHash = hashFunction(b);
long long rollingHash = hashFunction(a.substr(0, b.size()));
long long basePow = fastExp(BASE, b.size() - 1);
for (int i = 0; i <= (int) a.size() - b.size(); ++i){
if (rollingHash == bHash){
pos.push_back(i);
}
rollingHash = rollingHash - (basePow * (long long) a[i]) % MOD;
rollingHash += (rollingHash < 0) ? MOD : 0;
rollingHash = (rollingHash * BASE) % MOD;
rollingHash += (long long) a[i + b.size()];
}
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;
}