Cod sursa(job #2981486)

Utilizator juniorOvidiu Rosca junior Data 18 februarie 2023 07:04:52
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>

using namespace std;

string m, t;                         // modelul care se cauta, textul in care se cauta
int lp[2000001], s[1001], lm, i, ns; // lungimile prefixelor, solutiile
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

void kmp_table(string m) {
    int im = 0, ip = 0; // indice pentru model, indice pentru prefix
    char c = '\0';
    lp[0] = -1; // !! ca sa se avanseze in t folosind formula [*]
    while (im <= lm - 1) {
        if (m[im] == c) {
            lp[im + 1] = ip + 1;
            ip++;
            im++;
        }
        else //
            if (ip > 0)
                ip = lp[ip];
            else {
                lp[im + 1] = 0;
                ip = 0;
                im++;
            }
        c = m[ip];
    }
}

void kmp_search(string m, string t) {
    int it = 0, im = 0;
    int lt = t.size(), lm = m.size();
    while (it + im <= lt - 1) {  // cat timp nu depasim ultimul caracter
        if (t[it + im] == m[im]) // Caracterele se potrivesc.
            im++;                // Trecem sa comparam urmatorul caracter.
        else {                   // Caracterele nu se potrivesc.
            it += im - lp[im];   // noua pozitie in text [*]
            if (im > 0)
                im = lp[im];     // Mergem la primul loc unde nu am comparat.
        }
        if (im == lm) { // S-au potrivit toate caracterele.
            ns++;
            if (ns <= 999) 
                s[++ns] = it;
        }
    }
}

int main() {
    fin >> m >> t;
    lm = m.size();
    kmp_table(m);
    /*
      for (i = 1; i <= lm; i++)
        cout << lp[i];
      cout << '\n';
    */
    kmp_search(m, t);
    fout << ns << '\n';
    for (i = 1; i <= min(ns, 1000); i++)
        fout << s[i] << ' ';
}