Cod sursa(job #434235)

Utilizator hasegandaniHasegan Daniel hasegandani Data 5 aprilie 2010 14:06:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;

#define Nmax 2000005
#define Smax 1005

int N,K,pi[Nmax];
char A[Nmax],B[Nmax];
int sol[Smax],cnt;

void KMP()
{
    int k=0;
    for(int i=1;i<=N;++i)
        {
            while( k>0 && A[k+1]!=B[i])
                k=pi[k];
            if (A[k+1]==B[i])
                ++k;
            if (k==K)
                {
                ++cnt;
                if (cnt <= 1000)
                    sol[cnt]=i-K;
                }
        }
}

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

void init()
{
    K=strlen(A);
    for(int i=K;i;--i)
        A[i]=A[i-1];
    A[0]=' ';
    N=strlen(B);
    for(int i=N;i;--i)
        B[i]=B[i-1];
    B[0]=' ';
}

void afis()
{
    printf("%d\n",cnt);
    for(int i=1,M=min(cnt,1000);i<=M;++i)
        printf("%d ",sol[i]);
    printf("\n");
}

void cit()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",A);
    scanf("%s",B);
}

int main()
{
    cit();
    init();
    prefix();
    KMP();
    afis();
    return 0;
}