Cod sursa(job #2773683)

Utilizator ptudortudor P ptudor Data 8 septembrie 2021 12:42:18
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>
#define dbg(x...) cout << "[" << #x << "] = [ "; _dbg(x); cout << "]\n"
using namespace std;

template <typename T>void _dbg(T t){cout << t << " ";}template<typename T, typename... Args>void _dbg(T t, Args... args) {cout << t << " , ";_dbg(args...) ;}template <typename T, typename V>ostream& operator<<(ostream& os, const pair<T,V> p){cout << "(" << p.first << "," << p.second << ")";}template <template <typename...> class Container, typename... Types>ostream& operator<<(ostream& os, const Container<Types...> &dt){cout << "{";auto preEnd = dt.end();preEnd--;for (auto bgn = dt.begin(); bgn != preEnd; bgn++)cout << *bgn << ",";cout << *preEnd << "}";return os;}ostream& operator<<(ostream& os, const string &dt){cout << "{";auto preEnd = dt.end();preEnd--;for (auto bgn = dt.begin(); bgn != preEnd; bgn++)cout << *bgn;cout << *preEnd << "}";return os;}

ifstream in("strmatch.in");
ofstream out("strmatch.out");

vector<int> kmpPre(string s)
{int i;
    vector<int> pre(s.size() , 0);
    for (i = 1; i < s.size(); i++) {
        int k = pre[i - 1];
        while (k > 0 && s[i] != s[k]) {
            k = pre[k - 1];
        }
        if (s[k] == s[i])
            k++;
        pre[i] = k;
    }
    return pre;
}

string s,t;
void input()
{
    in >> t >> s;
   // dbg(s,t);
}
void solve()
{
    int j = 0,n = s.size(),i;
    vector<int> pre = kmpPre(t),matches;
    for (int i = 0; i < n;) {
        //dbg(i,j);
        if (s[i] == t[j]) {//cout << "MATCH\n\n";
            i++;
            j++;
            if (j == t.size()) {
                matches.push_back(i - t.size());
                j = pre[j - 1];
            }
        }
        else
        {
            if (j != 0)
                j = pre[j - 1];
            else
                i++;
        }
    }
    out << matches.size() << "\n";
    for (i = 0; i < min(1000 , (int)matches.size()); i++)
        out << matches[i] << " ";
    out << "\n";
}
int main()
{int t = 1;
    while (t--) {
        input();
        solve();
    }
}