Cod sursa(job #2764921)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 23 iulie 2021 16:10:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.48 kb
/*
    KMP
*/

#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

#define LMAX 2000000 //doua milioane

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

int nrSol;

int sol[1000 + 1];
int pref[LMAX];
char cuv[LMAX + 1];
char sir[LMAX + 1];
vector <int> solutii;

void computePref(char sir[], int N){
    pref[0] = 0;

    for(int i = 1; i < N; i++){
        int r = pref[i - 1];
        while(r != 0 && sir[r] != sir[i]){
            r = pref[r - 1];
        }

        if(sir[r] == sir[i]){
            pref[i] = r + 1;
        }
        else {
            pref[i] = 0;
        }
    }
}

void KMP(char sir[], char cuv[], int lgS, int lgC){
    int ct = 0;

    for(int i = 0; i < lgS; i++){
        while(ct != 0 && sir[i] != cuv[ct]){
            ct = pref[ct - 1];
        }
        if(sir[i] == cuv[ct]){
            ct++;
        }
        //else //ct = 0 daca se ajunge aici

        if(ct == lgC){
            nrSol++;
            if(nrSol <= 1000){
                sol[nrSol] = i - lgC + 1;
            }

            ct = pref[lgC - 1];
        }
    }
}

int main()
{
    fin.getline(cuv, LMAX + 1);
    fin.getline(sir, LMAX + 1);

    int lgC = strlen(cuv);
    int lgS = strlen(sir);

    computePref(cuv, lgC);
    KMP(sir, cuv, lgS, lgC);

    fout << nrSol << "\n";
    for(int i = 1; i <= nrSol; i++){
        fout << sol[i] << ' ';
    }
    return 0;
}