Cod sursa(job #1631368)

Utilizator calin1Serban Calin calin1 Data 5 martie 2016 15:19:08
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

char a[2000000], b[2000000];
int p[2000000],q[2000000],w;

void citire(char a[])
{
    char s[2000000];
    gets(s);
    a[0]='0';
    for(int i=0; i<strlen(s); i++)
    {
        a[i+1]=s[i];
    }
}

void creare()
{
    int j=0;
    for(int i=1; i<strlen(b); i++)
    {
        if(b[i+1]==b[j+1])
        {
            p[i+1]=j+1;
            j++;
        }
        else
        {
            while(b[j]!='0')
            {
                j=p[j];
                if(b[j+1]==b[i+1])
                {
                    p[i+1]=p[j+1]+1;
                    j++;
                    break;
                }
            }

        }

    }
//    for(int i=1; i<strlen(b); i++)
//    {
//        printf("%d",p[i]);
//    }
//    printf("\n");
//    for(int i=1; i<strlen(b); i++)
//    {
//        printf("%c",b[i]);
//    }
}
void comparare()
{
    int j=0,x=0,nr=0;
    for(int i=0; i<strlen(a); i++)
    {
        int z;
        if(a[i+1]==b[j+1])
        {
            if(j==0)
            {
                z=i;
            }
            x++;
            if(x==strlen(b)-1)
            {
                nr++;
                q[w++]=z;
                z=i;
            }
            j++;
        }
        else
        {
            x=0;
            while(b[j]!='0')
            {
                j=p[j];
                if(b[j+1]==a[i+1])
                {
                    x+=2;
                    j++;
                    break;
                }
            }

        }
    }


    printf("%d\n",nr);
    for(int i=0; i<w; i++)
    {
        printf("%d ",q[i]);
    }
}

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

    citire(b);
    citire(a);


    creare();
    comparare();

    return 0;
}