Cod sursa(job #2675091)

Utilizator alex02Grigore Alexandru alex02 Data 21 noiembrie 2020 10:00:27
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
#include <cstring>

#define NMAX 2000005
using namespace std;

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

char a[2000001], b[2000001];
int sol[1001], p[2000001], m, n;


int matchS() {
    int k = 0, nr = 0;

    for (int i = 1; i <= n; i++) {
        while (k > 0 && a[k + 1] != b[i])
            k = p[k];
        if (b[i] == a[k + 1])
            k++;
        if (k == m) {
            nr++;
            if (nr <= 1000)
                sol[nr] = i - m;
            k = p[k];
        }
    }
    return nr;
}

void afisare(int nr) {
    g << nr << '\n';
    nr = min(nr, 1000);
    for (int i = 1; i <= nr; i++)
        g << sol[i] << ' ';
}

void rezolvare() {
    int k = 0;

    p[1] = 0;
    for (int j = 2; j <= m; j++) {
        while (k > 0 && a[k + 1] != a[j])
            k = p[k];
        if (a[k + 1] == a[j]) {
            k++;
        }
        p[j] = k;
    }
}

void citire() {
    f.getline(a + 1, NMAX);
    f.getline(b + 1, NMAX);
    n = strlen(b + 1);
    m = strlen(a + 1);
}


int main() {
    rezolvare();
    int nr = matchS();
    afisare(nr);
    return 0;
}