Cod sursa(job #1123733)

Utilizator dumitrualexAlex Dumitru dumitrualex Data 26 februarie 2014 09:54:36
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 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(a);
    scanf("\n");
    gets(b);
    scanf("\n");

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

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

    while (i < n)
    {
        if (a[i-1] == 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;
    i = j = 0;
    while (i + j < m)
    {
        if (b[i+j] == a[i])
        {
            i++;
            if (i == n)
            {
                solutii.push_back(j);
                i = 0;
                j++;
            }
        }
        else
        {
            j = j + i - T[i];
            if (T[i] >= 0)
                i = T[i];
            else
                i = 0;
        }
    }
}

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();
    formareT();
    gasire();
    afisare();
    return 0;
}