Cod sursa(job #1263194)

Utilizator george.diaconuDiaconu Gerge george.diaconu Data 14 noiembrie 2014 01:33:12
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <string.h>
#include <fstream>
#define maxLength 2000010
using namespace std;

ifstream ji("date.in");
ofstream jo("date.out");

char A[maxLength], B[maxLength];
int sol[1005], pi[maxLength], m, n, total;

void buildPrefix()
{
    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;
    }
}

void solve()
{
    int q=0;
    for (int 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];
            if (total<1000)
                sol[total]=i-m;
            total++;
        }
    }
}

void show()
{
    jo << total << "\n";
    for (int i=0; i< (total<1000 ? total:1000); i++)
        jo << sol[i] << " ";
}

int main()
{
    ji >> A+1 >> B+1;
    m=strlen(A+1);
    n=strlen(B+1);
    buildPrefix();
    solve();
    show();
    return 0;
}

/*
* 6
* 7 9 11 13 15 31
*/