Cod sursa(job #1402660)

Utilizator razvanxdVancea Cosmin Razvan razvanxd Data 26 martie 2015 18:30:02
Problema Potrivirea sirurilor Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.4 kb
#include <stdio.h>

#define minim(a, b) ((a < b) ? a : b)
using namespace std;
// v - sir
// v1 - subsir

int p[2000002], m, n, pos[1000];
char v[2000002], v1[2000002];

void cauta()
{
    int q = 0;
    p[1] = 0;
    for(int i = 2; i <= m; ++i)
    {
        while(q != 0 && v1[q+1] != v[i])
            q = p[q];

        if(v1[q+1] == v[i])
            ++q;

        p[i] = q;
    }
}

void citeste()
{
    freopen("strmatch.in", "r", stdin);
    fgets(v1, sizeof(v1), stdin);
    fgets(v, sizeof(v), stdin);
    for (; (v1[n] >= 'A' && v1[n] <= 'Z') || (v1[n] >= 'a' && v1[n] <= 'z')
            || (v1[n] >= '0' && v1[n] <= '9'); ++n);
    for (; (v[m] >= 'A' && v[m] <= 'Z') || (v[m] >= 'a' && v[m] <= 'z')
            || (v[m] >= '0' && v[m] <= '9'); ++m);
    for (int i = n; i; --i) v1[i] = v1[i-1]; v1[0] = ' ';
    for (int i = m; i; --i) v[i] = v[i-1]; v[0] = ' ';
}

int numara()
{
    int nr = 0;
    for(int i = 1; i <= m; ++i)
    {
        if(p[i] == n)
        {
            if(nr < 1000)
                pos[nr] = i-n;
            ++nr;
        }
    }
    return nr;
}

void scrie()
{
    freopen("strmatch.out", "w", stdout);
    int n = numara()+1;
    printf("%d\n", n);
    for(int i = 0, j = minim(n, 1000); i < j; ++i)
        printf("%i ", pos[i]);
    printf("\n");
}

int main()
{
    citeste();
    cauta();
    scrie();
    return 0;
}