Pagini recente » Cod sursa (job #2238772) | Cod sursa (job #1121292) | Cod sursa (job #1239414) | Cod sursa (job #1565355) | Cod sursa (job #2025554)
#include <iostream>
#include <vector>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
const long long MOD = (long long) 2e9;
const long long BASE = 255;
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);
}
}
long long hashFunction(string s){
long long hashKey = 0;
long long baseFact = 1;
for (int i = s.size() - 1; i >= 0; --i){
hashKey = (hashKey + (baseFact * (long long) s[i]) % MOD) % MOD;
baseFact = (baseFact * BASE) % 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);
}
if (i != (int) (a.size() - b.size())){
rollingHash -= ((long long) a[i] * basePow) % MOD;
rollingHash += (rollingHash < 0) ? MOD * (-rollingHash / MOD + 1) : 0;
rollingHash = (rollingHash * BASE) % MOD;
rollingHash = (rollingHash + (long long) a[i + b.size()]) % MOD;
}
if (rollingHash < 0 ){
cout << rollingHash <<"\n";
}
}
return pos;
}
int main(){
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string a, b;
getline(cin, b);
getline(cin, a);
vector <int> strMatch = stringMatching(a, b);
cout << strMatch.size() << "\n";
for (auto& item : strMatch){
cout << item << " ";
}
return 0;
}