Cod sursa(job #2531609)

Utilizator batistaUPB-Oprea-Cosmin-Dumitru batista Data 26 ianuarie 2020 15:02:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.59 kb
/* https://infoarena.ro/problema/strmatch */
#include <fstream>
#include <cstring>

#define NMax 2000003
#define WMax  1000

using namespace std;

char subsir[NMax], sir[NMax];
int nextState[NMax], matchPos[NMax];

void build_finite_automata(char *s, int n)
{
    nextState[0] = nextState[1] = 0;

    for (int i = 1, state = 0; i < n; ++i) {
        while (0 < state && s[state] != s[i]) {
            state = nextState[state];
        }

        if (s[state] == s[i]) {
            state++;
        }

        nextState[i+1] = state;
    }
}

int kmp_match(char *subsir, int n, char *sir, int m)
{
    int numMatch = 0;

    for (int i = 0, state = 0; i < m; ++i) {
        while (0 < state && subsir[state] != sir[i]) {
            state = nextState[state];
        }

        if (subsir[state] == sir[i]) {
            state++;
        }

        if (state == n) {
            if (numMatch < WMax) {
                matchPos[numMatch] = i-n+1;
            }
            numMatch++;
            state = nextState[state];
        }
    }

    return numMatch;
}

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

    f.getline(subsir, NMax);
    f.getline(sir, NMax);

    int n = strlen(subsir);
    int m = strlen(sir);

    build_finite_automata(subsir, n);
    int numMatch = kmp_match(subsir, n, sir, m);

    g << numMatch << "\n";

    numMatch = (WMax < numMatch) ? WMax : numMatch;
    for (int i = 0; i < numMatch; ++i) {
        g << matchPos[i] << " ";
    }

    f.close();
    g.close();

    return 0;
}