Cod sursa(job #2078782)

Utilizator cristicretancristi cretan cristicretan Data 29 noiembrie 2017 22:38:24
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 2.64 kb
/// KMP COMPARARE DE SIRURI
#include <iostream>
#include <fstream>
#include <cstring>
#include <string>
#include <utility>
#include <algorithm>
#define NMax 2000001
///#define f cin
///#define g cout
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int A, B, v[NMax], ans, sol[NMax], foo;
char a[NMax], b[NMax];

int main()
{
    f.getline(a, NMax);
    f.getline(b, NMax);

    A = strlen(a); /// pattern-ul care trebuie verificat daca exista in text
    B = strlen(b); /// textul initial

    for(int i = 1; i < A;) /// construiesc vectorul temporar pentru pattern-ul care trebuie gasit
        if(a[i] == a[ans]) /// daca sunt egale (gasesc un prefix egal cu un sufix) atunci in vectorul temporar se adauga orice pozitie e ans + 1
        {
            v[i] = ans + 1;
            ++ans;
            ++i; /// si continuam sa verificam
        }
        else if(ans != 0) ans = v[ans - 1]; /// daca nu sunt egale te duci la valoarea de la caracterul dinainte si ans o sa devina valoarea aia ceea ce inseamna ca de acolo trebuie sa inceapa verificarea din nou
        else /// daca nu sunt egale pur si simplu setam valoarea cu 0 si continuam sa verificam
        {
            v[i] = 0;
            ++i;
        }

    if(A < 1000 && B < 1000)
    {
        int i_curent = 0, j_curent = 0;
        while(i_curent < B && j_curent < A)
        {
            if(b[i_curent] == a[j_curent]) ++i_curent, ++j_curent; /// daca sunt egale... continuam sa verificam
            else if(j_curent != 0) j_curent = v[j_curent - 1]; /// daca nu sunt egale si contorul pattern-ului e diferit de 0 atunci ii dam valoarea caracterului de dinainte
            else i_curent++; /// daca nu sunt egale continuam...
            if(j_curent == A) /// daca contorul e egal cu lungimea pattern-ului atunci adaugam solutie
            {
                sol[++foo] = i_curent - A; /// adugam pozitia de inceput unde e gasita aparitia si numaram solutia
                j_curent = 0; /// resetam contorul
                --i_curent;
            }
        }
    }
    else
    {
        int i_curent = 0, j_curent = 0;
        while(i_curent < B && j_curent < A)
        {
            if(b[i_curent] == a[j_curent]) ++i_curent, ++j_curent;
            else if(j_curent != 0) j_curent = v[j_curent - 1];
            else i_curent++;
            if(j_curent == 1000)
            {
                sol[++foo] = i_curent - 1000;
                j_curent = 0;
                --i_curent;
            }
        }
    }

    g << foo << '\n';

    for(int i = 1; i <= foo; ++i)
        g << sol[i] << " ";

    return 0;
}