Cod sursa(job #2151761)

Utilizator KemyKoTeo Virghi KemyKo Data 4 martie 2018 21:25:17
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define NMAX 2000001

using namespace std;

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

int n, m;
int T[NMAX];
char a[NMAX], b[NMAX];
vector <int> rez;

void prefix()
{
    int k = 0, i;

    for(i=2; i<=n; ++i) {
        while(k > 0 && a[k + 1] != a[i])
            k = T[k];
        if(a[k + 1] == a[i])
            ++k;
        T[i] = k;
    }
}

void KMP()
{
    int k = 0, i;

    for(i=1;i<=m;++i){
        while(k>0 && a[k + 1] != b[i])
            k = T[k];
        if(a[k + 1] == b[i])
            ++k;
        if(k==n){
            rez.push_back(i - n);
            k=T[k];
        }
    }
}

void afis()
{
    int i, sz = rez.size();

    g<<sz<<'\n';
    for(i=0;i<rez.size() && i<=1000;++i)
        g<<rez[i]<<' ';
}

int main()
{
    f.getline(a + 1, NMAX); //citire
    f.getline(b + 1, NMAX);
    n = strlen(a + 1);      //dimensiuni
    m = strlen(b + 1);

    if(n>m) {
        g<<'0';
        return 0;
    }

    prefix();           //precalc
    KMP();              //Search

    afis();
    return 0;
}