Pagini recente » Cod sursa (job #3197328) | Cod sursa (job #49976) | Cod sursa (job #1389645) | Cod sursa (job #3158914) | Cod sursa (job #3170952)
#include <fstream>
#include <vector>
#include <string>
#define ios ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#pragma gcc optimize("Ofast")
#pragma GCC optimization("Ofast")
#pragma optimize(Ofast)
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
const int MOD = 666013;
const int BASE = 256;
int cnt;
vector<int> rez;
void HashFunc(string pattern, string str){
int M = pattern.size();
int N = str.size();
int pattern_hash = 0;
int str_hash = 0;
int power = 1;
for(int i = 0; i < M - 1; i++)
power = (power * BASE) % MOD;
for (int i = 0; i < M; i++) {
pattern_hash = (BASE * pattern_hash + pattern[i]) % MOD;
str_hash = (BASE * str_hash + str[i]) % MOD;
}
int j;
for (int i = 0; i <= N - M; ++i) {
if (pattern_hash == str_hash) {
for (j = 0; j < M; ++j) {
if (str[i + j] != pattern[j])
break;
}
if (j == M)
rez.push_back(i);
cnt++;
}
if (i < N - M) {
str_hash = (BASE * (str_hash - str[i] * power) + str[i + M]) % MOD;
if (str_hash < 0)
str_hash += MOD;
}
}
}
signed main(){
ios;
string pattern, str;
cin >> pattern >> str;
HashFunc(pattern, str);
cout << cnt << '\n';
for (int i = 0; i < rez.size(); ++i) {
cout << rez[i] << ' ';
}
return 0;
}