Cod sursa(job #553393)

Utilizator mytzuskyMihai Morcov mytzusky Data 13 martie 2011 23:15:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <string.h>

#define nmax 2000010

using namespace std;

char A[nmax],B[nmax];
int n,m, b[nmax], p[nmax], N;

void Citire()
{
    freopen("strmatch.in","r",stdin);
    scanf("%s%s",&A,&B);
    n = strlen(A);
    m = strlen(B);
}

void Form()
{
    b[0]=-1;
    int i=0, j=-1;

    while(i<n)
    {
        while(j>=0 && A[i]!=A[j])
            j=b[j];
        i++, j++;
        b[i]=j;
    }
}

void Kmp()
{
    int i=0, j=0;

    while(i<m)
    {
        while(j>=0 && B[i]!=A[j])
            j=b[j];
        i++, j++;
        if(j==n)
        {
            N++;
            p[N]=i-j;
            j=b[j];
        }
    }
}

void Afis()
{
    freopen("strmatch.out","w",stdout);

    printf("%d\n",N);
    for(int k=1;k<=1000 && k<=N;k++)
        printf("%d ",p[k]);
    printf("\n");
}

int main()
{
    Citire();
    Form();
    Kmp();
    Afis();
    return 0;
}