Cod sursa(job #2178233)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 19 martie 2018 11:51:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>
    
using namespace std;
    
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

vector < int > zFind(const string &A, const string &B) {
    string eval = A + "$" + B;
    int n = (int)eval.size();
    vector < int > aux(n);

    for(int i = 1, lo = 0, hi = 0; i < n; ++i) {
        if(i <= hi) {
            aux[i] = min(hi - i + 1, aux[i - lo]);
        }
        while(i + aux[i] < n && eval[aux[i]] == eval[i + aux[i]]) {
            ++aux[i];
        }
        if(i + aux[i] - 1 > hi) {
            lo = i;
            hi = i + aux[i] - 1;
        }
    }

    vector < int > ret;
    for(int i = 0; i < n; ++i) {
        if(aux[i] == (int)A.size()) {
            ret.push_back(i - (int)A.size() - 1);
        }
    }

    return ret;
}

int main() {
    string A, B;
    fin >> A >> B;

    vector < int > ans = zFind(A, B);

    fout << (int)ans.size() << "\n";
    for(int i = 0; i < min((int)ans.size(), 1000); ++i) fout << ans[i] << " ";
    return 0;
}