Pagini recente » Diferente pentru utilizator/stargold2 intre reviziile 182 si 275 | Diferente pentru problema/nambartiori intre reviziile 102 si 57 | Monitorul de evaluare | Conexidad | Cod sursa (job #2277237)
#include <bits/stdc++.h>
#define NMAX 2000009
using namespace std;
#define USE_FILES 1
#ifdef USE_FILES
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define cin fin
#define cout fout
#endif // USE_FILES
string a, b;
char v[NMAX], T[NMAX];
int l1, l2, p[NMAX], sol;
set <int> s;
int main() {
cin >> a >> b;
l1 = a.size();
l2 = b.size();
for (int i = 0; i < l1; ++i) {
v[i + 1] = a[i];
}
for (int i = 0; i < l2; ++i) {
T[i + 1] = b[i];
}
int q = 0;
for (int i = 1; i <= l2; ++i) {
while (q && T[i] != v[q + 1]) {
q = p[q];
}
if (T[i] == v[q + 1]) {
++q;
}
p[i] = q;
if (q == l1) {
q = p[l1];
}
}
for (int i = 1; i <= l2; ++i) {
if (p[i] == l1) {
++sol;
s.insert(i - p[i]);
}
}
cout << sol <<'\n';
for (auto x : s) cout << x << ' ';
return 0;
}