Pagini recente » Cod sursa (job #3264387) | Cod sursa (job #1811017) | Cod sursa (job #2556655) | Cod sursa (job #494167) | Cod sursa (job #3183734)
#include <iostream>
#include <fstream>
#include <vector>
#define ll long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const ll MOD = 1e9 + 7;
ll p = 31;
ll putere[2000005];
string s, t;
ll hs, ht, n, m;
bool check(int ind) {
for (int i = ind; i < ind + n; i++) {
if (s[i - ind] != t[i])
return false;
}
return true;
}
vector<int> res;
int main() {
fin >> s >> t;
n = s.size();
m = t.size();
putere[0] = 1;
for (int i = 1; i <= n; i++) {
putere[i] = (putere[i - 1] * p) % MOD;
}
for (int i = n - 1; i >= 0; i--) {
hs = (hs + putere[n - i - 1] * (ll)(s[i] - 'A' + 1)) % MOD;
ht = (ht + putere[n - i - 1] * (ll)(t[i] - 'A' + 1)) % MOD;
}
//cout << hs << '\n';
for (int i = 0; i < m - n; i++) {
if (hs == ht) {
if (check(i))
res.push_back(i);
}
// cout << ht << ' ';
ht = (ht - putere[n - 1] * (ll)(t[i] - 'A' + 1) + MOD) % MOD;
ht = ((ht * p) % MOD + (t[i + n] - 'A' + 1)) % MOD;
}
int nr = res.size();
fout << nr << '\n';
for (int i = 0; i < min(1000, nr); i++)
fout << res[i] << ' ';
return 0;
}