Pagini recente » Cod sursa (job #1936379) | Cod sursa (job #335026) | Cod sursa (job #3206850) | Cod sursa (job #1574961) | Cod sursa (job #2921885)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define vt vector
#define pb push_back
#define em emplace
#define emb emplace_back
#define all(x) x.begin(), x.end()
#define all1(x) x.begin() + 1, x.end()
#define sz(x) (int)(x).size()
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
template <class T> void re(vt <T>& x);
template <class T> void re(T& x) {
cin >> x;
}
template <class H, class... T> void re(H &x, T&... y) {
re(x); re(y...);
}
template <class T> void re(vt <T>& x) {
for(auto& it : x)
re(it);
}
template <class T> void wr(T x) {
cout << x;
}
template <class H, class ...T> void wr(H x, T... y) {
wr(x); wr(y...);
}
inline void Open(const string Name) {
#ifndef ONLINE_JUDGE
(void)!freopen((Name + ".in").c_str(), "r", stdin);
(void)!freopen((Name + ".out").c_str(), "w", stdout);
#endif
}
void solve() {
auto prefix_function = [](const string &s) -> vt <int> {
int n = sz(s);
vt <int> p(n);
for (int i = 1;i < n;i++){
int k = p[i - 1];
while(k && s[i] != s[k])
k = p[k - 1];
k += (s[i] == s[k]);
p[i] = k;
}
return p;
};
string A, B; re(A, B);
int n = sz(A), m = sz(B), cnt = 0;
vt <int> p = prefix_function(A);
vt <int> ans;
for(int i = 0, k = 0;i < m;i++) {
while(k && B[i] != A[k])
k = p[k - 1];
k += (B[i] == A[k]);
if(k == n) {
k = p[k - 1]; ++cnt;
if(sz(ans) != 1000) {
ans.emb(i - n + 1);
}
}
}
wr(cnt, '\n');
for(auto& it : ans) {
wr(it, ' ');
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
Open("strmatch");
int t = 1;
for(;t;t--) {
solve();
}
return 0;
}