Cod sursa(job #1880508)

Utilizator savigunFeleaga Dragos-George savigun Data 15 februarie 2017 20:01:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <string.h>
using namespace std;

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

int n, lt, lp;
char pattern[2000000];
char text[2000000];
int prefix[2000000];
int pos[1001];

void preprocess();
void KMP();
void output();

int main() {
    in >> pattern;
    in >> text;

    lp = strlen(pattern);
    lt = strlen(text);

    preprocess();
    KMP();
    output();

    return 0;
}


void preprocess() {
    int j = 0;
    prefix[0] = 0;

    for (int i = 1; i < lp; ++i) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = prefix[j - 1];
        }

        if (pattern[i] == pattern[j]) {
            j++;
        }

        prefix[i] = j;
    }
}

void KMP() {
    int j = 0;
    for (int i = 0; i < lt; ++i) {
        while (j > 0 && text[i] != pattern[j]) {
            j = prefix[j - 1];
        }

        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == lp) {
            n++;
            if (n <= 1000) pos[n] = i - lp + 1;
            j = prefix[j - 1];
        }
    }
}


void output() {
    out << n << '\n';

    int mini = min(1000, n);
    for (int i = 1; i <= mini; ++i)
        out << pos[i] << " ";
}