Cod sursa(job #1161709)

Utilizator rares96cheseliRares Cheseli rares96cheseli Data 31 martie 2014 13:32:32
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");

int N, M, pi[2000005], dim, sol[2000005], k=0;
char A[2000005], B[2000005];

void build_pi()
{
    for (int i=2; i<=N; ++i)
    {
        while (k>0 && pi[k+1]!=A[i]) --k;
        if (A[k+1]==A[i]) ++k;
        pi[i]=k;
    }
}

int main()
{
    f>>(A+1); f>>(B+1); N=strlen(A+1); M=strlen(B+1);
    build_pi(); k=0;
    for (int i=1; i<=M; ++i)
    {
        while (k>0 && A[k+1]!=B[i]) --k;
        if (A[k+1]==B[i]) ++k;
        if (k==N)
            k=pi[N], sol[++dim]=i-N;
    }
    g<<dim<<'\n'; if (dim>1000) dim=1000;
    for (int i=1; i<=dim; ++i)
        g<<sol[i]<<' ';
    return 0;
}