Pagini recente » Cod sursa (job #331493) | Cod sursa (job #788225) | Cod sursa (job #2694668) | Cod sursa (job #1259733) | Cod sursa (job #2534390)
#include <bits/stdc++.h>
#define PRIME 31
#define MOD2 100007
#define MOD1 100021
std::pair <int, int> hash(const std::string &str) {
std::pair <int, int> ans(0, 0);
int p1 = 1, p2 = 1;
for (int i=str.size()-1; i>=0; --i)
ans.first = (ans.first + (str[i]-'A')*p1)%MOD1, p1 = (p1*PRIME)%MOD1,
ans.second = (ans.second + (str[i]-'A')*p2)%MOD2, p2 = (p2*PRIME)%MOD2;
return ans;
}
std::string t, s;
std::pair <int, int> hash_t;
std::ifstream input ("strmatch.in");
std::ofstream output("strmatch.out");
int main()
{
input >> t >> s;
int len_t = t.size();
hash_t = hash(t);
if (t.size() > s.size()) {
output << 0;
return 0;
}
int pp1 = 1, pp2 = 1;
for (int i=0; i<len_t; ++i)
pp1 = (pp1*PRIME)%MOD1, pp2 = (pp2*PRIME)%MOD2;
std::vector <int> sol;
std::pair <int, int> val = hash(s.substr(0, len_t));
if (val == hash_t) sol.push_back(0);
for (int i=len_t; i<s.size(); ++i) {
val.first = (val.first*PRIME + (s[i]-'A') - (s[i-len_t]-'A')*pp1 % MOD1 + MOD1)%MOD1;
val.second = (val.second*PRIME + (s[i]-'A') - (s[i-len_t]-'A')*pp2 % MOD2 + MOD2)%MOD2;
if (val == hash_t) sol.push_back(i-len_t+1);
}
output << sol.size() << '\n';
for (int i=0; i<sol.size() && i<1000; ++i)
output << sol[i] << ' ';
return 0;
}