Cod sursa(job #1123674)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 26 februarie 2014 09:37:11
Problema Potrivirea sirurilor Scor 32
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <cstdio>
#include <cstring>
#include <vector>
#define lmax 2000000+5
using namespace std;

char a[lmax], b[lmax];
int n, m;
int T[lmax];
vector<int> solutii;

void citire()
{
    gets(b);
    scanf("\n");
    gets(a);
    scanf("\n");

    n = strlen(a);
    m = strlen(b);
}

void formareT()
{
    int i, j;
    T[0] = -1;
    i = 1;
    j = 0;

    while (i < n)
    {
        if (a[i] == a[j])
        {
            j += 1;
            T[i] = j;
            i += 1;
        }
        else if (j > 0)
            j = T[j];
        else
        {
            T[i] = 0;
            i += 1;
        }
    }
}

void gasire()
{
    int i, j, k;
    i = j = 0;
    k = 0;
    while (i + j < n)
    {
        if (a[i+j] == b[j])
        {
            j++;
            k++;
            if (k == m)
            {
                solutii.push_back(i);
                j = k = 0;
                i++;
            }
        }
        else
        {
            k = 0;
            i = i + j - T[j];
            j = 0;
        }
    }
}

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

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

    citire();
    formareT();
    gasire();
    afisare();
    return 0;
}