Pagini recente » Cod sursa (job #2142740) | Cod sursa (job #2742617) | Cod sursa (job #2162169) | Istoria paginii runda/bibelcontest/clasament | Cod sursa (job #3172506)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#define ll long long
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const ll MOD = 1e9 + 7;
ll q = 26;
vector<ll> res;
void calcq(ll exp) {
ll res = 1;
while (exp--) {
res = (res * q) % MOD;
}
q = res;
}
ll val(char c) {
return (c - 'A' + 1);
}
int main() {
string a, b;
fin >> a >> b;
ll m = a.size(), n = b.size();
calcq(m - 1);
ll pattern_hash = 0;
ll text_hash = 0;
for (ll i = 0; i < m; i++) {
pattern_hash = (pattern_hash * 26 + val(a[i])) % MOD;
text_hash = (text_hash * 26 + val(b[i])) % MOD;
}
for (int i = 0; i < n - m ; i++) {
if (i >= 1) {
// scot vechea valoarea, o adauga pe cea noua
text_hash = ((((text_hash - q * val(b[i - 1]) + MOD) % MOD) * 26 % MOD) + val(b[i + m - 1])) % MOD;
}
// cout << text_hash << ' ';
if (pattern_hash == text_hash) {
bool match = true;
for (int j = i; j < i + m && match; j++) {
if (a[j - i] != b[j])
match = false;
}
if (match) {
res.push_back(i);
}
}
}
fout << res.size() << '\n';
for (int i = 0; i < min(1000LL, (ll)res.size()); i++) {
fout << res[i] << ' ';
}
return 0;
}