Cod sursa(job #1126418)

Utilizator macajouMaca George macajou Data 26 februarie 2014 23:13:32
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
#define nmax 2000010

using namespace std;

char N[nmax],M[nmax];
int n,m,nr,sol[nmax],key[nmax];

void prefix()
{
    int x=0,i;
    key[1]=0;
    for(i=2;i<=n;i++)
        {
            while(x>0 && N[x+1]!=N[i])
                  x=key[x];
            if(N[x+1]==N[i])
               x++;
            key[i]=x;
        }
}

void match()
{
    int i,x=0;
    for(i=1;i<=m;i++)
        {
            while(x>0 && N[x+1]!=M[i])
                  x=key[x];
            if(N[x+1]==M[i])
               x++;
            if(x==n)
               sol[++nr]=i-n;
        }
}

void afisare()
{
    int i;
    printf("%d\n",nr);
    for(i=1;i<=nr;i++)
        printf("%d ",sol[i]);
}

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

    gets(N+1);
    n=strlen(N+1);
    gets(M+1);
    m=strlen(M+1);
    prefix();
    match();
    afisare();

    return 0;
}