Cod sursa(job #604714)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 24 iulie 2011 17:44:57
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include <iostream>
#include <string>

#define LMax 2000005

using namespace std;

char A[LMax], B[LMax];
int N, M, Pi[LMax], NMatch, Match[1005];

void Read ()
{
    freopen ("strmatch.in", "r", stdin);
    scanf ("%s\n%s", &A, &B);
    N=strlen (A);
    M=strlen (B);
    for (int i=N; i>0; --i)
    {
        A[i]=A[i-1];
    }
    for (int i=M; i>0; --i)
    {
        B[i]=B[i-1];
    }
}

void Print ()
{
    freopen ("strmatch.out", "w", stdout);
    printf ("%d\n", NMatch);
    for (int i=1; i<=1000 and i<=NMatch; ++i)
    {
        printf ("%d ", Match[i]-1);
    }
    printf ("\n");
}

void BuildPi ()
{
    int k=0;
    Pi[1]=0;
    for (int i=2; i<=N; ++i)
    {
        while (k>0 and A[k+1]!=A[i])
        {
            k=Pi[k];
        }
        if (A[i]==A[k+1])
        {
            ++k;
        }
        Pi[i]=k;
    }
}

void KMP ()
{
    int k=0;
    BuildPi ();
    for (int i=1; i<=M; ++i)
    {
        while (k>0 and B[i]!=A[k+1])
        {
            k=Pi[k];
        }
        if (B[i]==A[k+1])
        {
            ++k;
        }
        if (k==N)
        {
            ++NMatch;
            if (NMatch<=1000)
            {
                Match[NMatch]=i;
            }
        }
    }
}

int main()
{
    Read ();
    KMP ();
    Print ();
    return 0;
}