Cod sursa(job #2971921)

Utilizator HandoMihnea-Vicentiu Hando Data 28 ianuarie 2023 12:47:28
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 5.26 kb
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define ar array
#define vt vector
#define pq priority_queue
#define pu push
#define pub push_back
#define em emplace
#define emb emplace_back

#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define allp(x, l, r) x.begin() + l, x.begin() + r
#define len(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, size_t N>
void re(array <T, N>& x);
template <class T> 
void re(vt <T>& x);

template <class T> 
void re(T& x) {
    cin >> x;
}

template <class T, class... M> 
void re(T& x, M&... args) {
    re(x); re(args...);
}

template <class T> 
void re(vt <T>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void re(array <T, N>& x) {
    for(auto& it : x)
        re(it);
}

template <class T, size_t N>
void wr(array <T, N> x);
template <class T> 
void wr(vt <T> x);

template <class T> 
void wr(T x) {
    cout << x;
}

template <class T, class ...M>  void wr(T x, M... args) {
    wr(x), wr(args...);
}

template <class T> 
void wr(vt <T> x) {
    for(auto it : x)
        wr(it, ' ');
}

template <class T, size_t N>
void wr(array <T, N> x) {
    for(auto it : x)
        wr(it, ' ');
}


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() {
    /* An algorithm which follows the definition of prefix function exactly is the following: 
        vector<int> prefix_function(string s) {
            int n = (int)s.length();
            vector<int> pi(n);
            for (int i = 0; i < n; i++)
                for (int k = 0; k <= i; k++)
                    if (s.substr(0, k) == s.substr(i-k+1, k))
                        pi[i] = k;
            return pi;
        }

        It is easy to see that its complexity is O(n^3), which has room for improvement.
        
        The first important observation is, that the values of the prefix function can only increase by at most one.
        Thus when moving to the next position, the value of the prefix function can either increase by one, stay the same, or decrease by some amount. 
        This fact already allows us to reduce the complexity of the algorithm to O(n^2), because in one step the prefix function can grow
        at most by one. In total the function can grow at most n steps, and therefore also only can decrease a total of n steps.
        This means we only need to perform O(n) string comparisons, and reach the complexity O(n^2).

        Let's go further, we want to get rid of the string comparisons. To accomplish this, we have to use all the information computed in the previous steps.
        So let us compute the value of the prefix function pi for i + 1. If s[i + 1] = s[pi[i]], then we can say with certainty that
        pi[i + 1] = pi[i] + 1, since we already know that the suffix at position i of length pi[i] is equal to the prefix of length pi[i].
        
        If this not the case, s[i + 1] != s[pi[i]], then we need to try a shorter string. In order to speed things up, we would like to
        immediately move to the longest length j < pi[i], such that the prefix property in the position i holds, i.e.
        s[0...j - 1] = s[i - j + 1...i].

        Here is the final procedure:
            * We compute the prefix values pi[i] in a loop by iterating from i = 1 to n - 1 (pi[0] just gets assigend 0).
            * To calculate the cur. value pi[i] we set the variable j denoting the length of the best suffix for i - 1. Initially j = pi[i - 1].
            * Test if the suffix of length j + 1 is also a prefix by comparing s[j] and s[i]. If they are equal then we assign pi[i] = j + 1,
            otherwise we reduce j to pi[j - 1] and repeat this step.
            * If we have reached the length j = 0 and still don't have a match, then we assign pi[i] = 0 and go to the next index i + 1.
    */
    function <vt <int>(string)> prefix_function = [](string s) {
        vt <int> pi(len(s));
        for (int i = 1; i < len(s); ++i) {
            int j = pi[i - 1];
            while (j > 0 and s[i] != s[j]) {
                j = pi[j - 1];
            }
            if (s[i] == s[j])
                ++j;
            pi[i] = j;
        }
        return pi;
    };

    string a, b; re(a, b);
    if (len(a) > len(b)) {
        swap(a, b);
    }

    vt <int> pi = prefix_function(a);
    vt <int> res; int cnt = 0;
    for (int i = 0, j = 0; i < len(b); ++i) {
        while (j > 0 and b[i] != a[j]) {
            j = pi[j - 1];
        }

        if(b[i] == a[j]) {
            ++j;
        }

        if (j == len(a)) {
            ++cnt;
            if (len(res) < 1000) {
                res.emb(i - len(a) + 1);
            }
            j = pi[j - 1];
        }
    }

    wr(cnt, '\n', res);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    Open("strmatch");

    int t = 1;
    for(;t;t--) {
        solve();
    }
    
    return 0;
}