Pagini recente » Cod sursa (job #2920704) | Cod sursa (job #522131) | Cod sursa (job #3172007) | Cod sursa (job #796959) | Cod sursa (job #2309575)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;
ifstream f ("strmatch.in");
ofstream g ("strmatch.out");
const int NMAX = 2e6 + 5;
vi ans;
int nw, ns;
int pi[NMAX];
char w[NMAX], s[NMAX];
void computePi() {
pi[1] = 0;
int cnd = 0;
for (int i = 2; i <= nw; ++i) {
while (cnd && w[cnd + 1] != w[i]) {
cnd = pi[cnd];
}
if (w[cnd + 1] == w[i]) {
++cnd;
}
pi[i] = cnd;
}
}
void kmp() {
int cnd = 0;
for (int i = 1; i <= ns; ++i) {
while (cnd && w[cnd + 1] != s[i]) {
cnd = pi[cnd];
}
if (w[cnd + 1] == s[i]) {
++cnd;
}
if (cnd == nw) {
ans.pb (i - nw + 1);
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen (".in", "r", stdin);
#endif
f.getline (w + 1, NMAX);
f.getline (s + 1, NMAX);
nw = strlen (w + 1);
ns = strlen (s + 1);
computePi();
kmp();
g << ans.size() << '\n';
for (int i = 0; i < min (ans.size(), 1000u); ++i) {
g << ans[i] - 1 << ' ';
}
f.close();
g.close();
return 0;
}