Pagini recente » Cod sursa (job #50463) | Cod sursa (job #261971) | Cod sursa (job #1753613) | Cod sursa (job #2819113) | Cod sursa (job #1456962)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s, r;
const int p1 = 100003, p2 = 666013, b1 = 157, b2 = 233;
int vaca1 = 1, vaca2 = 1, look1, look2, cod1, cod2, cnt;
vector <int> sol;
int main() {
fin >> s >> r;
int l1 = s.size(), l2 = r.size();
for (int i = 1; i <= l1; i++) {
look1 = (look1 + vaca1 * s[l1 - i]) % p1;
look2 = (look2 + vaca2 * s[l1 - i]) % p2;
if(i < l1) {
vaca1 = (vaca1 * b1) % p1;
vaca2 = (vaca2 * b2) % p2;
}
}
for (int i = 0; i < l2; i++)
if (i < l1) {
cod1 = (cod1 * b1 + r[i]) % p1;
cod2 = (cod2 * b2 + r[i]) % p2;
} else {
if (cod1 == look1 && cod2 == look2) {
cnt++;
if(sol.size() < 1000)
sol.push_back(i - l1);
}
cod1 = (b1 * (cod1 + p1 - (vaca1 * r[i - l1]) % p1) + r[i]) % p1;
cod2 = (b2 * (cod2 + p2 - (vaca2 * r[i - l1]) % p2) + r[i]) % p2;
}
if(cod1 == look1 && cod2 == look2) {
cnt++;
if (sol.size() < 1000)
sol.push_back(l2 - l1);
}
fout << cnt << '\n';
for (auto it : sol)
fout << it << ' ';
return 0;
}