Pagini recente » Cod sursa (job #1524866) | Cod sursa (job #40880) | Cod sursa (job #2493714) | Cod sursa (job #1647558) | Cod sursa (job #3251431)
#pragma region TEMPLATES
#include <bits/stdc++.h>
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
void init() {
srand(time(0));
#ifdef ONLINE_JUDGE
cin.tie(0)->sync_with_stdio(0);
#else
freopen( "in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}
#ifdef ONLINE_JUDGE
#define debug(...) 69420
#define init_test(...) 69420
#else
void init_test(int t) {
cerr << "\nTEST #" << t << "\n";
}
template<typename T>
T debug(T n) {
cerr << n << " ";
return n;
}
template<typename T, typename... Args>
T debug(T n, Args... args) {
cerr << n << " ";
debug(args...);
return n;
}
void debug() {
cerr << "\n";
}
#endif
void solve();
int main() {
init();
int t = 1;
// cin >> t;
for (int i = 1; i <= t; ++i) {
init_test(i);
solve();
}
}
#pragma endregion TEMPLATES
void solve() {
// freopen("strmatch.in", "r", stdin);
// freopen("strmatch.out", "w", stdout);
string A, B;
cin >> A >> B;
int n = A.size();
int m = B.size();
vector<int> pref(n);
pref[0] = 0;
for (int i = 1; i < n; ++i) {
int k = pref[i - 1];
while (k != 0 && A[i] != A[k]) {
k = pref[k];
}
if (A[k] == A[i]) {
++k;
}
pref[i] = k;
}
int ct = 0;
vector<int> ans;
int k = 0;
for (int i = 0; i < m; ++i) {
while (k != 0 && B[i] != A[k]) {
k = pref[k - 1];
}
if (B[i] == A[k]) {
++k;
}
if (k == n) {
++ct;
if (ct <= 1000)
ans.push_back(i - n + 1);
k = pref[n - 1];
}
}
cout << ct << "\n";
for (int i = 0; i < ct; ++i) {
cout << ans[i] << " ";
}
}