Pagini recente » Cod sursa (job #1644845) | Cod sursa (job #2469804) | Cod sursa (job #1170577) | Monitorul de evaluare | Cod sursa (job #3356940)
#include<fstream>
#include<iostream>
#include<vector>
#define mod1 100019
#define mod2 100043
#define p 256
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
vector<int> sol;
int main() {
string s, t;
fin >> s >> t;
int n = s.size(), m = t.size();
int hash1 = 0, hash2 = 0;
int h1 = 0, h2 = 0;
int p1 = 1, p2 = 1;
if (m < n) {
fout << "0" << '\n';
return 0;
}
for (int i = 0; i < n; i ++) {
hash1 = (hash1 * p + s[i]) % mod1;
hash2 = (hash2 * p + s[i]) % mod2;
h1 = (h1 * p + t[i]) % mod1;
h2 = (h2 * p + t[i]) % mod2;
if (i != 0) {
p1 = p1 * p % mod1;
p2 = p2 * p % mod2;
}
}
if (h1 == hash1 && h2 == hash2) {
sol.push_back(0);
}
for (int i = n; i < m; i ++) {
h1 = ((h1 - (t[i-n] * p1) % mod1 + mod1) * p + t[i])% mod1;
h2 = ((h2 - (t[i-n] * p2) % mod2 + mod2) * p + t[i])% mod2;
if (h1 == hash1 && h2 == hash2) {
sol.push_back(i - n + 1);
}
}
fout << sol.size() << '\n';
for (int i = 0; i < min((int)sol.size(), 1000); i++) {
fout << sol[i] << ' ';
}
}