Cod sursa(job #1308544)

Utilizator bogdanciurezubogdan ciurezu bogdanciurezu Data 4 ianuarie 2015 12:58:22
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <cstring>
#include <stdio.h>
#include <cstring>
#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 make_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;
    }
}

int main()
{
    int i, q = 0;
    char delim = '\n';

    f.get(A, 2000, delim);
    f.get();
    f.get(B, 2000, delim);
    N = strlen(A);
    M = strlen(B);
    for(i = N + 1 ; i >= 1 ; --i)
        A[i] = A[i - 1];
    for(i = M + 1 ; i >= 1 ; --i)
        B[i] = B[i - 1];

    make_pref();

    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];
        }
    }

    g<<nr<<'\n';
    for(i = 1 ; i <= minim(nr, 1000) ; ++i)
        g<<solutii[i]<<' ';
    return 0;
}