Cod sursa(job #2178216)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 19 martie 2018 11:38:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 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) {
            lo = hi = i;
            while(i + aux[i] < n && eval[aux[i]] == eval[lo + aux[i]]) {
                ++aux[i];
                ++hi;
            }
            --hi;
        } else {
            if(i + aux[i - lo] > hi) {
                lo = i; 
                aux[i] = hi - i;
                while(i + aux[i] < n && eval[aux[i]] == eval[lo + aux[i]]) {
                    ++aux[i];
                    ++hi;
                }
                --hi;
            } else {
                aux[i] = aux[i - lo];
            }
        }
    }

    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;
}