Cod sursa(job #480835)

Utilizator PavelRazvanPavel Razvan PavelRazvan Data 29 august 2010 19:53:26
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.99 kb
#include<algorithm>
using namespace std;

#define DIM 2000005
#define DIM2 1005

char a[DIM],b[DIM];
int n,m,s[DIM],sol[DIM2],vf;

void read ()
{
    fgets (a,sizeof(a),stdin);
    fgets (b,sizeof(b),stdin);
    for(n=0;('0'<=a[n] && a[n]<='9') || ('A'<=a[n] && a[n]<='Z') || ('a'<=a[n] && a[n]<='z');++n);
    for(m=0;('0'<=b[m] && b[m]<='9') || ('A'<=b[m] && b[m]<='Z') || ('a'<=b[m] && b[m]<='z');++m);
}

void kmp ()
{
    int i,q=0;
    for(i=0;i<m;++i)
    {
        while(q && a[q+1]!=b[i])
            q=s[q];
        if(a[q+1]==b[i])
            ++q;
        s[i]=q;
    }
    for(i=0;i<m;++i)
    {
        if(s[i]==n-1)
            sol[++vf]=i-n+1;
        if(vf==1000)
            return ;
    }
}

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

int main ()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    read ();
    kmp ();
    show ();
    return 0;
}