Cod sursa(job #1711996)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 1 iunie 2016 19:13:00
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <cstring>

#define MAX_LENGTH 2000005
using namespace std;

char text[MAX_LENGTH], pattern[MAX_LENGTH];
size_t patternLg, textLg, nrMatches;
size_t matches[1005];
int pi[MAX_LENGTH];

inline int min(int x, int y){
    return (x < y) ? x : y;
}
void MakePi(){
    int k = -1;
    pi[0] = -1;
    for (int i = 1; i < patternLg; ++i){
        while (k >= 0 && pattern[i] != pattern[k + 1]){
            k = pi[k];
        }
        if (pattern[i] == pattern[k + 1]) ++k;
        pi[i] = k;
    }
}

void SearchText(){
    int k = -1;

    for (int i = 0; i < textLg; ++i){

        while (k >= 0 && pattern[k + 1] != text[i]){
            k = pi[k];
        }

        if (pattern[k + 1] == text[i]) ++k;
        if (k == patternLg - 1){
            if (nrMatches < 1000){
                matches[nrMatches] = i - k;
            }
            ++nrMatches;
            k = pi[k];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);

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

    fin.getline(pattern, MAX_LENGTH);
    fin.getline(text, MAX_LENGTH);

    patternLg = strlen(pattern);
    textLg = strlen(text);

    MakePi();
    SearchText();

    fout << nrMatches << '\n';
    for (int i = 0; i < min(nrMatches, 1000); ++i){
        fout << matches[i] << ' ';
    }
    return 0;

}