Cod sursa(job #1444150)

Utilizator mouse_wirelessMouse Wireless mouse_wireless Data 29 mai 2015 11:55:50
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.38 kb
#include <cstdio>
#include <cassert>
#include <cstring>
#include <algorithm>
#define _submit
#ifdef _submit
#define InFile "strmatch.in"
#define OutFile "strmatch.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif
 
#define MAXLEN 2010000
 
char str[MAXLEN], pat[MAXLEN];
int slen, patlen;
int F[MAXLEN];
int matches[1000];
int mnr = 0;
 
void buildFail() {
    F[0] = -1;
    F[1] = 0;
    for (int i = 2; i <= patlen; i++) {
        if (pat[i - 1] == pat[F[i - 1]])
            F[i] = F[i - 1] + 1;
        else
            F[i] = 0;
    }
}
 
void KMP() {
    int m = 0, i = 0;
    while (m + i < slen) {
        if (i < patlen && str[m + i] == pat[i]) {
            if (i == patlen - 1) {
		if(mnr < 1000)
			matches[mnr] = m;
                mnr++;
	    }
            i++;
        }
        else {
            if (i == 0)
                m++;
            else {
                m += i - F[i];
                i = F[i];
            }
        }
    }
}
 
int main() {
    assert(freopen(InFile, "r", stdin));
    assert(freopen(OutFile, "w", stdout));
    scanf("%s%s", pat, str);
    slen = strlen(str);
    patlen = strlen(pat);
    buildFail();
    KMP();
    printf("%d\n", mnr);
    int nrprint = std::min(mnr, 1000);
    for (int i = 0; i < nrprint; i++)
        printf("%d ", matches[i]);
    printf("\n");
    return 0;
}