Cod sursa(job #1026053)

Utilizator heracleRadu Muntean heracle Data 10 noiembrie 2013 23:17:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <cstdio>
#include <cstring>

const int Q=2000006;
char word[Q],text[Q];
int w,t,rez[Q] ;

int gr[Q];

void gres()
{
    int f;
    for(int i=2; i<=w; i++)
    {
        if(gr[i-1]==0)
        {
            if(word[i-1]==word[gr[i-1]])
                gr[i]=1;
        }
        else
        {
            if(word[i-1]==word[gr[i-1]])
                gr[i]=gr[i-1]+1;
            else
            {
                f=gr[gr[i-1]];
                while(f!=0)
                {
                    if(word[i-1]==word[f])
                    {
                        gr[i]=f+1;
                        break;
                    }
                    f=gr[f];
                }
            }
        }
    }

}


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

    scanf("%s\n%s",&word,&text);
    w=strlen(word);
    t=strlen(text);
    if(w>t)
    {
        printf("0");
        return 0;
    }
    gres();

    int nr=0,pozact=0;
    for(int i=0; i<t; i++)
    {
        if(pozact==w)
        {
            nr++;
            rez[++rez[0]]=i;
            pozact=gr[pozact];
        }

        if(text[i]==word[pozact])
        {
            pozact++;
        }
        else
        {
            pozact=gr[pozact];
            while(pozact!=0)
            {
                if(text[i]==word[pozact])
                {
                    pozact++;
                    break;
                }
                pozact=gr[pozact];
            }
            if(pozact==0 && text[i]==word[0])
                pozact++;
        }

    }
    if(pozact==w)
    {
        nr++;
        rez[++rez[0]]=t;
    }
    printf("%d\n",nr);

    for(int i=1; i<=rez[0]; i++)
    {
        printf("%d ",rez[i]-w);
    }

    return 0;
}