Cod sursa(job #1830839)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 17 decembrie 2016 10:48:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <cstring>

using namespace std;
char sub[2000005],str[2000005];
int pattern[2000005];
int len1, len2;
int rezultate[2000005], NrRez=0;

void makePattern()
{
    int x=0, y=1;
    pattern[0]=0;
    while(y<len1)
    {
        if(sub[x]==sub[y])
        {
            pattern[y]=x+1;
            x++;
            y++;
        }
        else
            if(x == 0)
            y++;
            else
        {
            x= pattern[x-1];
            while(x > 0)
            {
                if(sub[x] != sub[y])
                    x= pattern[x-1];
                else
                {
                    pattern[y]=x+1;
                    y++;
                    break;
                }
            }
        }
    }
}

void searchPattern()
{
    int x=0, y=0;

    while( y < len2)
    {
        if(sub[x]== str[y])
        {
            x++;
            y++;
        }
        else
            if(x!=0)
                x=pattern[x-1];
            else
                y++;
        if(x==len1)
            rezultate[NrRez++]=y-len1;
    }
    printf("%d\n", NrRez);
    if(NrRez>1000)
        NrRez=1000;
    for(int i=0; i<NrRez; i++)
        printf("%d ", rezultate[i]);
}
int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s", sub, str);
    len1=strlen(sub);
    len2=strlen(str);
    makePattern();
    searchPattern();
//        for(int i = 0; i < len1; i++)
//    {
//        printf("%d  ", pattern[i]);
//    }
    return 0;
}