Cod sursa(job #2056343)

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

using namespace std;
ifstream fin("input.txt");
ofstream fout("output.txt");
int pi[1001],M,N,i,n,pos[1001];
char A[1001],B[1001];

#define NMax 20000005

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)
        fout<<pos[i]<<' ';
    fout<<'\n';

    return 0;
}