Cod sursa(job #2056386)

Utilizator natrovanCeval Marius natrovan Data 4 noiembrie 2017 11:26:08
Problema Potrivirea sirurilor Scor 38
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define NMax 2000001

int pi[NMax],M,N,i,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()
{
    fin.getline(A,NMax);
    fin.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();

    int i,q=0;
    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;
        }
    }

    fout<<n<<'\n';
    for(i=1;i<=n;++i)
        if(pos[i]!=0)
        fout<<pos[i]<<' ';
    fout<<'\n';

    fin.close();fout.close();
    return 0;
}