Cod sursa(job #218371)

Utilizator mircea_infoSuciu Mircea-Gabriel mircea_info Data 1 noiembrie 2008 18:54:36
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <cstdio>
#include <cstring>
#define MAXIMUS 2000002

using namespace std;

char s[MAXIMUS],s1[MAXIMUS];
int nr,poz[MAXIMUS],k,sol[1001],zz;
int l1,l2;

void pref()
{
    for(int i=1;i<l1;i++)
    {
        while(k && s[k]!=s[i])
            k=poz[k];
        if(s[k]==s[i])
            k++;
        poz[i+1]=k;
    }
}

void cauta()
{
    k=0;
    for(int i=0;i<l2;i++)
    {
        while(k && s[k]!=s1[i])
            k=poz[k];
        if(s[k]==s1[i])
            k++;
        if(k==l1)
        {
            nr++;
            if(zz<1000)
                sol[zz++]=i-l1+1;
            k=poz[k];
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n%s",s,s1);
    l1=strlen(s);
    l2=strlen(s1);
    pref();
    cauta();
    printf("%d\n",nr);
    for(int i=0;i<zz;i++)
        printf("%d ",sol[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}