Cod sursa(job #2063111)

Utilizator cristii2000cristiiPanaite Cristian cristii2000cristii Data 11 noiembrie 2017 09:35:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 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();

    return 0;
}