Cod sursa(job #2674171)

Utilizator eugen_ptrEugen Patru eugen_ptr Data 18 noiembrie 2020 18:34:03
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.32 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;

#define MAXLENGTH 2000001

char T[MAXLENGTH], P[MAXLENGTH];
int N, LPS[MAXLENGTH], result[MAXLENGTH];
int lenT, lenP;

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

void calculateLongestPrefixSubfix() {
    int i=1;
    int j=0;
    LPS[0] = 0;
    while (i < lenP) {
        if (P[i] == P[j]) {
            LPS[i] = LPS[i-1] + 1;
            i++;
            j++;
        }
        else if (j != 0) {
            j=LPS[j-1];
        }
        else {
            i++;
        }

    }
}

void KMP() {
    int i=0;
    int j=0;

    while (i<lenT) {
        if(T[i] == P[j]) {
            i++;
            j++;
        } else if (j != 0) {
            j=LPS[j-1];
        } else {
            i++;
        }
        if (j == lenP) {
            result[N] = i-j;
            N++;
            j = LPS[j-1];
        }
    }
}

void afisare() {
    fout<<N<<endl;
    if (N > 1000) {
        N = 1000;
    }
    for (int i=0; i<N; i++) {
        fout<<result[i]<<" ";
    }
}

int main()
{
    fin.getline(P, MAXLENGTH);
    fin.getline(T, MAXLENGTH);
    lenT = strlen(T);
    lenP = strlen(P);

    calculateLongestPrefixSubfix();
    KMP();
    afisare();

    return 0;
}