Cod sursa(job #2879279)

Utilizator QwertyDvorakQwerty Dvorak QwertyDvorak Data 28 martie 2022 13:04:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back

#define dbg(x) cout << #x <<": " << x << "\n";
using ll = long long;

const string fn = "strmatch";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

string t, pat;
vector<int> ans;

vector<int> prefix(string s){
    vector<int> pi;
    pi.resize((int)s.size());
    for (int i = 1; i < (int)s.size(); ++i){
        int j = pi[i - 1];
        while(j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if(s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int main(){

// ABA#CABBCABABAB
// 012345678901234

    fin >> pat >> t;
    vector<int> pi((int)pat.size());
    string s = pat + "#" + t;
    pi = prefix(s);

    for (int i = 0; i < (int)s.size(); ++i)
        if(pi[i] == pat.size())
            ans.pb(i - ((int)pat.size() + (int)pat.size()));
    fout << ans.size() << '\n';
    for(auto i : ans)
        fout << i << " ";

    return 0;
}