Cod sursa(job #1406709)

Utilizator Celebrii_AnonimiUPB IONITA UNGUREANU IRIMIA Celebrii_Anonimi Data 29 martie 2015 17:26:06
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <cstdlib>

using namespace std;

#define N_MAX                           2000001

char A[N_MAX], B[N_MAX];

typedef struct t_matches {
    int len, pos[N_MAX];
} t_matches;

t_matches m;

void computeLps(char *pat, int m, int *lps)
{
    int i = 1, len = 0;
    lps[0] = 0;
    while (i < m) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
    }
}

void KMP(char *pat, char *str, t_matches *matches)
{
    matches->len = 0;

    int m = strlen(pat), n = strlen(str);
    int *lps = (int *) malloc(m * sizeof(int));

    computeLps(pat, m, lps);

    int i = 0, j = 0;
    while (i < n) {
        if (str[i] == pat[j]) {
            ++i, ++j;
        }
        if (j == m) {
            matches->pos[matches->len++] = i - j;
            j = lps[j - 1];
        } else if ((i < n) && (str[i] != pat[j])) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                ++i;
            }
        }
    }

    free(lps);
}

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

    fin >> A >> B;
    KMP(A, B, &m);

    fout << m.len << "\n";
    for (int i = 0; i < m.len; ++i) {
        fout << m.pos[i] << " ";
    }
    fout << "\n";

    return 0;
}