Pagini recente » Cod sursa (job #3215851) | Cod sursa (job #1867358) | Cod sursa (job #2961683) | Cod sursa (job #1697303) | Cod sursa (job #2787403)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
typedef long long ll;
string s, micut;
class Hash {
private:
ll n = 123457, m = 666013, power = 0, value = 0;
public:
Hash() {
power = value = 0;
}
void init(const string X) {
power = 1;
value = 0;
for(int i = X.length() - 1; i + 1; --i) {
value = (value + power * X[i] % m) % m;
if(i) power = power * n % m;
}
}
void roll(const char toRem, const char toAdd) {
value = (((value - (1ll * toRem * power) % m + m) * n) % m + toAdd) % m;
}
bool operator==(const Hash &X) const {
return value == X.value;
}
};
int main()
{
fin >> micut >> s;
string crt = s.substr(0, micut.length());
Hash mh;
mh.init(micut);
Hash sh;
sh.init(crt);
vector<int> ans;
for(int i = micut.length() - 1; i < s.length(); ++i) {
if(sh == mh) {
ans.push_back(i - micut.length() + 1);
}
if(i < s.length() - 1)
sh.roll(s[i - micut.length() + 1], s[i + 1]);
}
int n = min(1000, (int)ans.size());
fout << ans.size() << "\n";
for(const auto &el : ans) {
if(!n) break;
fout << el << " ";
n--;
}
return 0;
}