Cod sursa(job #1125551)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 26 februarie 2014 18:21:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define lmax 2000000+5
using namespace std;

char mic[lmax], mare[lmax];
int nMic, nMare;
int cheie[lmax];
vector<int> solutii;

void citire()
{
    gets(mic+1);
    scanf("\n");
    gets(mare+1);
    scanf("\n");

    nMic = strlen(mic+1);
    nMare = strlen(mare+1);
}

void formareCheie()
{
    int i, x;
    for (i = 2, x = 0; i <= nMic; i++)
    {
        while (x && mic[x+1] != mic[i])
            x = cheie[x];
        if (mic[x+1] == mic[i])
            x++;
        cheie[i] = x;
    }
}

void kmp()
{
    int i, x;
    for (i = 1, x = 0; i <= nMare; i++)
    {
        while (x && mic[x+1] != mare[i])
            x = cheie[x];
        if (mic[x+1] == mare[i])
            x++;
        if (x == nMic)
        {
            x = cheie[x];
            solutii.push_back(i-nMic);
        }
    }
}

void afisare()
{
    int i;
    printf("%d\n", solutii.size());
    for (i = 0; i < solutii.size() && i < 1000; i++)
        printf("%d ", solutii[i]);
    printf("\n");
}

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

    citire();
    formareCheie();
    kmp();
    afisare();
    return 0;
}