Cod sursa(job #1105237)

Utilizator eugen_ptrEugen Patru eugen_ptr Data 11 februarie 2014 17:06:45
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <iostream>
#include <cstdio>
#include <cstring>

#define Nmax 2000005

using namespace std;

char a[Nmax],b[Nmax];
int n,m;
int pi[Nmax];
int aparitii;
int pos[Nmax];

void citire()
{
    scanf("%s\n",a+1);
    scanf("%s\n",b+1);
    a[0] = ' ';
    b[0] = ' ';
    m = strlen(a);
    n = strlen(b);
    m--;
    n--;
}

void make_prefix()
{
    int q = 0;
    pi[1] = 0;

    for (int i=2; i<=m; i++)
    {
        while(q && a[q+1] != a[i])
            q = pi[q];
        if (a[q+1] == a[i])
            q++;
        pi[i] = q;
    }
}

void afisare()
{
    printf("%d\n",aparitii);
    for (int i=1; i<=aparitii; i++)
        printf("%d ",pos[i]);
}

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

    int q = 0;
    for (int i=1; i<=n; i++)
    {
        while(q && a[q+1] != b[i])
            q = pi[q];
        if (a[q+1] == b[i])
            q++;
        if (q == m)
        {
            aparitii++;
            q = pi[m];
            if (aparitii <= 1000)
                pos[aparitii] = i - m;
        }
    }

    afisare();

    return 0;
}