Pagini recente » Cod sursa (job #3337608) | Cod sursa (job #2873104) | Cod sursa (job #289241) | Cod sursa (job #3325076) | Cod sursa (job #3328381)
#include <bits/stdc++.h>
using namespace std;
const int mod1 = 100007;
const int mod2 = 100021;
int v[200005];
int main() {
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s1, s2;
cin >> s1 >> s2;
int sz1 = s1.size();
int sz2 = s2.size();
int p1 = 1, p2 = 1, nrs1,nrs2;
nrs1 = nrs2 = 0;
int cnt = 0;
for (int i = 0; i < sz1; i++) {
nrs1 = (nrs1 * 73 + s1[i]) % mod1;
nrs2 = (nrs2 * 73 + s1[i]) % mod2;
if (i!=0) {
p1 = (p1 * 73) % mod1;
p2 = (p2 * 73) % mod2;
}
}
int nr1 = 0, nr2 = 0;
for (int i = 0; i < sz1; i++) {
nr1 = (nr1 * 73 + s2[i]) % mod1;
nr2 = (nr2 * 73 + s2[i]) % mod2;
}
cnt = 0;
if (nr1 == nrs1 && nr2 == nrs2) {
cnt++;
v[cnt] = 0;
}
for(int i = 0; i < sz2 - sz1 + 1; i++) {
nr1 = ((nr1 - s2[i] * p1) % mod1 + mod1) % mod1;
nr2 = ((nr2 - s2[i] * p2) % mod2 + mod2) % mod2;
nr1 = (nr1 * 73 + s2[i + sz1]) % mod1;
nr2 = (nr2 * 73 + s2[i + sz1]) % mod2;
if (nr1 == nrs1 && nr2 == nrs2) {
cnt++;
v[cnt] = i;
}
}
if (sz1 > sz2) {
cout << "0\n";
}
else {
cout << cnt << "\n";
for (int i = 1; i <= cnt; i++) {
cout << v[i] + 1 << " ";
}
}
return 0;
}