Cod sursa(job #1193128)

Utilizator ZenusTudor Costin Razvan Zenus Data 30 mai 2014 23:43:01
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <cstdio>
#include <cstring>

using namespace std;

#define NMAX 2000010

char A[NMAX],B[NMAX];
int pi[NMAX],sol[NMAX];
int N,M;

void Build_pi()
{
    int k=0;

    pi[1]=0;

    for (int i=2;i<=N;++i)
    {
        while (k && A[i]!=A[k+1]) k=pi[k];

        if (A[k+1]==A[i]) ++k;

        pi[i]=k;
    }
}

void KMP()
{
    int k=0;

    Build_pi();

    for (int i=1;i<=M;++i)
    {
        while (k && B[i]!=A[k+1]) k=pi[k];

        if (B[i]==A[k+1]) ++k;

        if (k==N) sol[++sol[0]]=i-N;
    }

    printf("%d\n",sol[0]);
    for (int i=1;i<=sol[0];++i) printf("%d ",sol[i]);
    printf("\n");

}

int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);

gets(A+1);
gets(B+1);
N=strlen(A+1);
M=strlen(B+1);

KMP();

return 0;
}