Cod sursa(job #2178212)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 19 martie 2018 11:36:20
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 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 && (int)ret.size() < 1000; ++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(auto x: ans) fout << x << " ";
    return 0;
}