Cod sursa(job #1830804)

Utilizator SolcanMihaiSolcan Mihai Andrei SolcanMihai Data 17 decembrie 2016 10:18:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.2 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

char sir1[2000005];
char sir2[2000005];

int sirx1[2000005];
int sirx2[2000005];

int lungime1 = 0;
int lungime2 = 0;

void citire()
{
    fgets(sir1, 2000005, stdin);
    sir1[strlen(sir1) - 1] = 0;

    fgets(sir2, 2000005, stdin);
    sir2[strlen(sir2) - 1] = 0;

    lungime1 = strlen(sir1);
    lungime2 = strlen(sir2);
}

void construire()
{
    int x, y;
    sirx1[0] = 0;
    x = 0;
    y = 1;
    while(y < lungime1)
    {
        if(sir1[x] == sir1[y])
        {
            sirx1[y] = x + 1;
            x++;
            y++;
        }
        else
        {
            if(x == 0)
            {
                y++;
            }
            else
            {
                x = sirx1[x - 1];

                while(x > 0)
                {
                    if(sir1[x] != sir1[y])
                    {
                        x = sirx1[x - 1];
                    }
                    else
                    {
                        sirx1[y] = x + 1;
                        y++;
                        break;
                    }
                }
            }
        }
    }

//    for(int i = 0; i < lungime1; i++)
//    {
//        printf("%d", sirx1[i]);
//    }
}

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

    int nr = 0;
    vector<int> rez;

    while(y < lungime2)
    {
        if(sir1[x] == sir2[y])
        {
            x++;
            y++;
        }
        else
        {
            if(x != 0)
            {
                x = sirx1[x - 1];
            }
            else
            {
                y++;
            }
        }

        if(x == lungime1)
        {
            nr++;
            rez.push_back(y - lungime1);
        }
    }

    printf("%d\n", nr);

    int lim = nr;

    if(lim > 1000)
    {
        lim = 1000;
    }

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

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

    citire();
    construire();
    cautare();

    return 0;
}