Cod sursa(job #3206189)

Utilizator Theo20067Cismaru Theodor-Alexe Theo20067 Data 21 februarie 2024 20:27:12
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
///ALGORITMUL KMP
#include <fstream>
#include <vector>
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout("strmatch.out");
int lps[2000003];///cel mai lung prefix "propriu" (fara ultimul caracter) si in acelasi timp
int i,j,nr;      /// sufix al stringului pattern[0...j]
///acest rationament functioneaza deoarece daca doua string-uri dau mismatch la un caracter
///ca sa poti continua, stringul pana la valoarea anterioara precalculata din lsp[j-1]
///trb sa fie prefix a stringukui curent (pt ca trebuie sa dea match cu un substring din text)
///dar sa ii fie si sufix pentru a "inlocui" stringul si a continua liniar in text, desi cu o
///lungime matched mai mica evident
string pattern,text;
vector <int> sol;
int main()
{
    fin>>pattern;
    fin>>text;
    j=0;
    for(i=1;i<pattern.size();i++)///precalculare de lps in pattern
    {
        while(pattern[i]!=pattern[j]&&j>0)///cat timp cele doua caractere dau mismatch
            j=lps[j-1];                   ///incercam cu pozitia anterioara precalculata
        if(pattern[i]==pattern[j])///daca dau match putem continua de la pozitia j din pattern
            j++;
        lps[i]=j;
    }
    j=0;
    for(i=0;i<text.size();i++)///odata ce avem precalcularea finalizata, mai avem de aplicat pe text
    {
        while(text[i]!=pattern[j]&&j>0)
            j=lps[j-1];
        if(text[i]==pattern[j])
            j++;
        if(j==pattern.size())///daca j ajunge la lungimea pattern-ului, inseamna ca este cu un
        {
            nr++;
            if(nr<=1000)
                sol.push_back(i-j+1);///caracter in afara, adica a gasit un match in text si adaugam la solutie
        }
    }
    fout<<nr<<"\n";
    for(i=0;i<sol.size();i++)
        fout<<sol[i]<<" ";
    return 0;
}