Pagini recente » Cod sursa (job #2914070) | Cod sursa (job #1090560) | Cod sursa (job #1850356) | Cod sursa (job #1071908) | Cod sursa (job #3242088)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
namespace
{
#define ll long long
#define int ll
#undef INT_MAX
#define INT_MAX LLONG_MAX
#define ull unsigned long long
#define PI acos(-1)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vector<int>>
#define vf vector<long double>
#define vvf vector<vector<long double>>
#define cmplxd complex<double>
#define float long double
#define fs first
#define sc second
#define pb push_back
#define lsh(i) (1 << (i))
#define fi(i, n) for (int i = 0; (i) < (n); ++(i))
#define fe(x, a) for (auto &x : (a))
#define all(a) (a).begin(), (a).end()
#define YES (cout << "YES\n")
#define NO (cout << "NO\n")
#define endl '\n'
#define gcd(a, b) __gcd(a, b)
const int mod = (1e9 + 7);
const int pmod = 998244353;
const int altmod = 999999937;
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
struct custom_hash
{
static uint64_t splitmix64(uint64_t x)
{
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
size_t operator()(pair<uint64_t, uint64_t> x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x.first + FIXED_RANDOM) ^ (splitmix64(x.second + FIXED_RANDOM) >> 1);
}
};
#define us unordered_set<int, custom_hash>
#define um unordered_map<int, int, custom_hash>
void multiply(vvi &Z, vvi B)
{
int N = Z.size();
vvi A(Z);
Z = vvi(N, vi(N, 0));
fi(i, N)
fi(j, N)
fi(k, N)
Z[i][j] = (Z[i][j] + 1ll * A[i][k] * B[k][j] % altmod) % altmod;
}
[[maybe_unused]] void f(vvi &Z, int n)
{
vvi aux(Z);
while (n)
{
if (n % 2)
multiply(Z, aux);
multiply(aux, aux);
n /= 2;
}
}
}
void solve()
{
int n;
cin >> n;
int w;
cin >> w;
vi p(n - 1);
fe(x, p)
{
cin >> x;
}
int ans = w * n;
int k = w, last = 0;
fi(i, n - 1)
{
int x, d;
cin >> x >> d;
k -= d;
ans -= k;
ans -= d * (n - 2 - i);
// ans += last;
cout << ans << ' ';
last = d;
}
cout << endl;
}
signed main()
{
#ifndef ONLINE_JUDGE
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
#endif // ! ONLINE_JUDGE
ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
cout.tie(nullptr);
// int t;
// cin >> t;
// while (t--)
// {
// solve();
// }
string t, s;
cin >> t >> s;
int m = t.size(), n = s.size();
vector<int> p(m, 0);
for (int i = 1, j = 0; i < m;)
{
if (t[i] == t[j])
{
p[i] = p[j] + 1;
i++, j++;
}
else
{
if (j == 0)
{
p[i] = 0;
i++;
}
else
{
j = p[j - 1];
}
}
}
int ans_sz = 0;
vector<int> ans;
for (int i = 0, j = 0; i < n;)
{
if (s[i] == t[j])
{
i++, j++;
}
else
{
if (j == 0)
{
i++;
}
else
{
j = p[j - 1];
}
}
if (j == m)
{
ans_sz++;
if (ans_sz <= 1000)
{
ans.push_back(i - m);
}
}
}
cout << ans_sz << endl;
fe(x, ans)
{
cout << x << ' ';
}
return 0;
}