Pagini recente » Cod sursa (job #2161730) | Cod sursa (job #543424) | Cod sursa (job #2035113) | Cod sursa (job #1622638) | Cod sursa (job #1456956)
#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 + 1LL * vaca1 * s[l1 - i]) % p1;
look2 = (look2 + 1LL * vaca2 * s[l1 - i]) % p2;
if(i < l1) {
vaca1 = (1LL * vaca1 * b1) % p1;
vaca2 = (1LL * vaca2 * b2) % p2;
}
}
for (int i = 0; i < l2; i++)
if (i < l1) {
cod1 = ((1LL * cod1 * b1) + r[i]) % p1;
cod2 = ((1LL * cod2 * b2) + r[i]) % p2;
} else {
if (cod1 == look1 && cod2 == look2) {
cnt++;
if(sol.size() < 1000)
sol.push_back(i - l1);
}
cod1 = (cod1 + p1 - (1LL * vaca1 * r[i - l1]) % p1) % p1;
cod1 = (1LL * cod1 * b1 + r[i]) % p1;
cod2 = (cod2 + p2 - (1LL * vaca2 * r[i - l1]) % p2) % p2;
cod2 = (1LL * cod2 * b2 + 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;
}