Cod sursa(job #3242088)

Utilizator StasBrega Stanislav Stas Data 8 septembrie 2024 16:59:00
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.4 kb
#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;
}