Cod sursa(job #1406977)

Utilizator MrWhiteDELETEME MrWhite Data 29 martie 2015 17:53:33
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 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";
    if (m.len > 1000) {
        m.len = 1000;
    }
    for (int i = 0; i < m.len; ++i) {
        fout << m.pos[i] << " ";
    }
    fout << "\n";

    return 0;
}