Pagini recente » Cod sursa (job #2224714) | Cod sursa (job #2217418) | Cod sursa (job #124713) | Cod sursa (job #128087) | Cod sursa (job #2803261)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NHASH1 = 100007;
const int NHASH2 = 100021;
const int BHASH = 63;
const int NMAX = 2000000;
int Adauga(int h, char ch, int base, int MOD) {
return ((h * base) % MOD + ch) % MOD;
}
int Sterge(int h, char ch, int pow, int MOD) {
return (h - (ch * pow) % MOD + MOD) % MOD;
}
int lgput(int a, int b, int MOD) {
int ans = 1;
while(b != 0) {
if(b & 1)
ans = (1LL * ans * a) % MOD;
a = (1LL * a * a) % MOD;
b /= 2;
}
return ans;
}
int main() {
int p_hash1, s_hash1, p_hash2, s_hash2;
string pattern, s;
fin >> pattern >> s;
int n = s.size();
int m = pattern.size();
int pow1 = lgput(BHASH, m - 1, NHASH1);
int pow2 = lgput(BHASH, m - 1, NHASH2);
p_hash1 = s_hash1 = p_hash2 = s_hash2 = 0;
for(int i = 0; i < m; i++) {
p_hash1 = Adauga(p_hash1, pattern[i], BHASH, NHASH1);
s_hash1 = Adauga(s_hash1, s[i], BHASH, NHASH1);
p_hash2 = Adauga(p_hash2, pattern[i], BHASH, NHASH2);
s_hash2 = Adauga(s_hash2, s[i], BHASH, NHASH2);
}
vector<int> sol;
if(s_hash1 == p_hash1 && s_hash2 == p_hash2)
sol.push_back(0);
for(int i = m; i < n; i++) {
s_hash1 = Adauga(Sterge(s_hash1, s[i - m], pow1, NHASH1), s[i], BHASH, NHASH1);
s_hash2 = Adauga(Sterge(s_hash2, s[i - m], pow2, NHASH2), s[i], BHASH, NHASH2);
if(s_hash1 == p_hash1 && s_hash2 == p_hash2)
sol.push_back(i - m + 1);
}
fout << sol.size() << "\n";
for(int i = 0; i < sol.size() && i < 1000; i++)
fout << sol[i] << " ";
return 0;
}