Cod sursa(job #2056383)

Utilizator gandacbucatarieAndrei Candet gandacbucatarie Data 4 noiembrie 2017 11:25:21
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <fstream>
#include <string.h>

using namespace std;

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

#define NMAX 2000005

int i, q, n, pi[NMAX], M, N, pos[NMAX];
char A[NMAX], B[NMAX];

void prefix(){
    int i, q=0;

    for(i=2, pi[1] = 0; i<=M; ++i){
        while(q && A[q+1] != A[i]) q=pi[q];
        if(A[q+1]==A[i])++q;
        pi[i]=q;
    }
}


int main()
{
    f.getline(A,NMAX);
    f.getline(B,NMAX);
    M=strlen(A);
    N=strlen(B);

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

    prefix();

    for(i=1; i<=N; ++i){
        while(q && A[q+1]!=B[i]) q = pi[q];
        if(A[q+1]==B[i]) ++q;
        if(q==M)
        {
            q=pi[M];
            ++n;
            pos[n]=i-M;
        }
    }

    g<<n<<'\n';
    if(n>1000) n=1000;
    for(i=1; i<=n; ++i) g<<pos[i]<<' ';
    g<<'\n';

    return 0;
}