Pagini recente » Cod sursa (job #1207413) | Cod sursa (job #1465269) | Cod sursa (job #192368) | Cod sursa (job #1094271) | Cod sursa (job #3237984)
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
const char nl = '\n';
const char sp = ' ';
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const string out[2]{ "No", "Yes" };
#define all(a) a.begin(), a.end()
#define var(a) #a
#define dbg(a) cerr << var(a) << " = " << a << nl
#define OK() cerr << "OK until line " << __LINE__ << nl
using ll = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
auto start_time = chrono::high_resolution_clock::now();
double getTime() {
auto end_time = chrono::high_resolution_clock::now();
return chrono::duration<double>(end_time - start_time).count();
}
template<typename T>
int rand(T a, T b) { return uniform_int_distribution<T>(a, b)(rng); }
template<typename T1, typename T2>
bool ckmax(T1& a, T2 b) { return a < b ? a = b, true : false; }
template<typename T1, typename T2>
bool ckmin(T1& a, T2 b) { return a > b ? a = b, true : false; }
const int nmax = 2e6;
int n, m;
string s, t;
int lps[nmax * 2 + 5];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
fin >> s >> t;
n = s.size();
m = t.size();
s = '#' + s;
t = '#' + t;
s += t;
int len = n + m + 1;
for (int i = 2; i <= len; ++i) {
int j = lps[i - 1];
while (j > 0 && s[j + 1] != s[i]) {
j = lps[j];
}
if (s[j + 1] == s[i]) {
++j;
}
lps[i] = j;
}
vector<int> occ;
for (int i = n + 2; i <= len; ++i) {
if (lps[i] == n) {
occ.push_back(i - 2 * n - 1);
}
}
fout << occ.size() << nl;
if (occ.size() > 1000) {
occ.resize(1000);
}
for (auto& x : occ) {
fout << x << sp;
}
}