Pagini recente » Cod sursa (job #2653183) | Istoria paginii runda/3333333333 | Cod sursa (job #2640488) | Cod sursa (job #2660739) | Cod sursa (job #2266751)
#include <bits/stdc++.h>
#define Nmax 40000009
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
int z[Nmax];
string a,b;
char P[Nmax];
set <int> s;
void strbuild(string a, string b) {
int l1 = a.size();
int l2 = b.size();
for (int i = 0; i < l1; ++i) {
P[i + 1] = a[i];
}
P[l1+1] = '#';
for (int i = 0; i < l2; ++i) {
P[l1 + i + 2] = b[i];
}
}
void Z(char P[Nmax], int n) {
z[1] = 0;
int l = 0, r = 0;
for (int i = 2; i <= n; ++i) {
if (i <= r) {
z[i] = min(z[i - l], r - i + 1);
}
while (i + z[i] - 1 <= n && P[i + z[i]] == P[z[i] + 1]) {
++z[i];
}
if (i + z[i] - 1 >= r) {
r = i + z[i] -1;
l = i;
}
}
}
int main() {
cin >> a >> b;
int l1 = a.size();
int l2 = b.size();
strbuild(a, b);
int n = l1 + l2 +1;
// for (int i = 1; i <= n; ++i) cout << P[i];
Z(P, n);
int cnt = 0;
for (int i = 1; i <= n; ++i) {
if (z[i] == l1) {
++cnt;
s.insert(i);
}
}
cout << cnt << '\n';
for (auto x: s) cout << x - l1 - 2 << ' ';
return 0;
}