Cod sursa(job #1303833)

Utilizator diana97Diana Ghinea diana97 Data 28 decembrie 2014 14:24:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

const int NMAX = 2000000 + 5;

int nr;
int sol[1000 + 1];
int F[NMAX];
char s[NMAX], p[NMAX];

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

void proceseaza(char pattern[]) {
    F[0] = 0;
    int k = 0, m = strlen(pattern);
    for (int q = 1; q < m; q++) {
        while (k > 0 && pattern[k] != pattern[q]) k = F[k - 1];
        if (pattern[k] == pattern[q]) k++;
        F[q] = k;
    }
}

void KMP(char s[], char p[]) {
    int q = 0;
    int n = strlen(s);
    int m = strlen(p);
    proceseaza(p);
    for (int i = 0; i < n; i++) {
        while(q > 0 && p[q] != s[i]) q = F[q - 1];
        if (p[q] == s[i]) q++;
        if (q == m) {
            if (++nr <= 1000) {
                sol[nr] = i - m + 1;
            }
        }
    }
}

void citeste() {
    f >> p >> s;
}

void scrie() {
    g << nr << '\n';
    for (int i = 1; i <= 1000 && i <= nr; i++) g << sol[i] << ' ';
}

int main() {
    citeste();
    KMP(s, p);
    scrie();
    return 0;
}