Cod sursa(job #973986)

Utilizator supermitelArdelean Razvan Mitel supermitel Data 16 iulie 2013 11:00:30
Problema Potrivirea sirurilor Scor 16
Compilator cpp Status done
Runda Arhiva educationala Marime 2.16 kb
#include <cstdio>
#include <cstring>

using namespace std;

int key[2000005], na, nb, n;
char a[2000005], b[2000005];
int sol[1000000];

/*struct element
{
    int inf;
    element *urm;
    element(int x = 0)
    {
        inf = x;
        urm = NULL;
    }
};

struct lista
{
    element *root, *last;
}sol;

void push(lista &q, int val)
{
    if(q.root == NULL)
    {
        q.root = new element(val);
        q.last = q.root;
    }
    else
    {
        q.last -> urm = new element(val);
        q.last = q.last -> urm;
    }
}*/

void make_key()
{
    int k = 0;
    for(int i = 1; i < na; i++)
    {
        if(!k)
        {
            while(a[i]!=a[0])
                i++;
        }
        if(i < na && a[k] == a[i])
            ++k;
        else k = 0;
        key[i+1] = k;
    }
}

void solve()
{
    int k = 0;
    for(int i = 0; i <= nb; i++)
    {
        /*if(k)
        {
            if(k == na)
            {
                //n++;
                //push(sol, i - na);
                sol[n++] = i-na;
            }
            if(a[k] == b[i])
                k++;
            else
            {
                k = key[k];
                if(k) i--;
            }
        }
        if(!k)
        {
            k = 1;
            while(b[i] != a[0] && i < nb)
                i++;
        */
        if(k == na)
            sol[n++] = i-na;
        if(!k)
        {
            while(b[i]!=a[0])
                i++;
            k++;
        }
        else while(k && i<nb)
        {
            if(a[k] == b[i])
                ++k, ++i;
            else k = key[k];
            if(k == na)
                sol[n++] = i-na;
        }
    }
}

void afis()
{
    printf("%d\n", n);
    /*for(element *p = sol.root; p; p = p -> urm)
        printf("%d ", p -> inf);
    printf("\n");*/
    for(int i = 0; i< n; i++)
        printf("%d ", sol[i]);
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s\n", a, b);
    na = strlen(a);
    nb = strlen(b);
    make_key();
    solve();
    afis();
    return 0;
}