Cod sursa(job #1308577)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 4 ianuarie 2015 13:45:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.34 kb
#include <fstream>
#include <cstring>
#include <stdio.h>
#define nmax 2000500
#define minim(a, b) ((a < b) ? a : b)
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int N, M, pr[nmax], nr, solutii[2000];
char A[nmax], B[nmax];

void pref(){

    int q = 0, i;

    for(i = 2 , pr[1] = 0 ; i <= N ; ++i){
        while(q && A[q + 1] != A[i])
            q = pr[q];
        if(A[q + 1] == A[i])
            ++q;
        pr[i] = q;
    }
}
void KMP(){
    int i, q = 0;
    for(i = 1 ; i <= M ; ++i){

        while(q && A[q + 1] != B[i])
            q = pr[q];
        if(A[q + 1] == B[i])
            ++q;
        if(q == N){

            ++nr;
            if(nr <= 1000)
                solutii[nr] = i - q;
            q = pr[N];
        }
    }
}
int main()
{
    int i;
    FILE *fin, *fout;
    fin = fopen("strmatch.in", "r");
    fout = fopen("strmatch.out", "w");

    fgets(A, sizeof(A), fin);
    fgets(B, sizeof(B), fin);

    N = strlen(A) - 1;
    M = strlen(B) - 1;

    for(i = N ; i >= 1 ; --i)
        A[i] = A[i - 1];
    for(i = M ; i >= 1 ; --i)
        B[i] = B[i - 1];

    pref();
    KMP();

    fprintf(fout, "%d\n", nr);
    for (i = 1; i <= minim(nr, 1000); ++i) {
        fprintf(fout, "%d ",solutii[i]);
    }
    fprintf(fout, "\n");
    return 0;
}