Cod sursa(job #2749524)

Utilizator flibiaVisanu Cristian flibia Data 6 mai 2021 23:38:02
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.42 kb
// g++ -std=c++17 -DLOCAL a.cpp -o ex && ./ex >tst.out 2>&1
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
 
string to_string(const string& s) {
    return '"' + s + '"';
}
 
string to_string(const char* s) {
    return to_string((string) s);
}
 
string to_string(bool b) {
    return (b ? "true" : "false");
}
 
string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for (int i = 0; i < static_cast<int>(v.size()); i++) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}
 
template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for (size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}
 
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for (const auto &x : v) {
        if (!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
    return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
 
void debug_out() { cerr << "   "; }
void debug_out_nl() { cerr << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

template <typename Head, typename... Tail>
void debug_out_nl(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out_nl(T...);
}
 
#ifdef LOCAL
#define dbg(...) cerr << "#" << #__VA_ARGS__ << ":", debug_out(__VA_ARGS__)
#define nl(...) cerr << "#" << #__VA_ARGS__ << ":", debug_out_nl(__VA_ARGS__)
#else
#define dbg(...) 69
#define nl(...) 42
#endif

#define ll long long
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll st, ll dr) {
    assert(st <= dr);
    return st + rng() % (dr - st + 1);
}

const int MOD = 1e9 + 7;
const int N = 2e5 + 10;
const int MAX = 1000; 

struct KMP {
    string s;
    vector<int> lps; // lps[i] - lungimea la cel mai lung prefix care e si sufix pentru s[0..i], 0-indexed

    KMP(const string &_s) : s(_s), lps(_s.size(), 0) {
        build();
    }

    // construieste lps
    void build() {
        int len = 1;
        for (int i = 1; i < s.size(); i++) {
            while (len > 1 && s[i] != s[len - 1]) {
                len = lps[len - 1];
            }

            if (s[len - 1] == s[i]) {
                lps[i] = len++;
            } else {
                lps[i] = len;
            }
        }
    }

    // returneaza aparitiile lui s in target, 0-indexed
    vector<int> match(const string &target) {
        vector<int> sol;
        for (int i = 0, p = 0; i < target.size(); i++) {
            while (p > 0 && s[p] != target[i]) {
                p = lps[p] - 1;
            }

            if (s[p] == target[i]) {
                p++;
            }

            if (p == s.size()) {
                sol.push_back(i - s.size() + 1);
                p = lps[p - 1];
            }
        }

        return sol;
    }
};

void solve(int test, istream &cin, ostream &cout) {
    string a, b;
    cin >> a >> b;

    KMP matcher(a);
    auto sol = matcher.match(b);
    
    cout << sol.size() << '\n';
    for (int i = 0; i < min(MAX, (int) sol.size()); i++) {
        cout << sol[i] << ' ';
    }

    // cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

int main() {
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    bool multiTest = false;

    int t;    
    if (multiTest) {
        cin >> t;
    } else {
        t = 1;
    }

    for (int test = 1; test <= t; test++) {
        solve(test, cin, cout);
    }

    return 0;
}