Cod sursa(job #2375458)

Utilizator MichaelXcXCiuciulete Mihai MichaelXcX Data 8 martie 2019 09:39:50
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include    <stdio.h>
#include    <string.h>

#define     MAXN 2000010
#define     minim(a, b) ((a < b) ? a : b)

using namespace std;

int M, N;
char a[MAXN], b[MAXN];
int pi[MAXN], pos[1024];

void makePrefix(void)
{
    int i, q = 0;
    for(i = 2, pi[1] = 0; i <= M; ++i)
    {
        while(q && a[q + 1] != a[i])
            q = pi[q];
        if(a[q+1] == a[i])
            ++q;
        pi[i] = q;
    }
}

int main(void)
{
    int i, q = 0, n = 0;

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

    fgets(a, sizeof(a), stdin);
    fgets(b, sizeof(b), stdin);

    for(; (a[M] >= 'A' && a[M] <= 'Z') ||
          (a[M] >= 'a' && a[M] <= 'z') ||
          (a[M] >= '0' && a[M] <= '9'); M++)
    for(; (b[N] >= 'A' && b[N] <= 'Z') ||
          (b[N] >= 'a' && b[N] <= 'z') ||
          (b[N] >= '0' && b[N] <= '9'); N++)
    for(i = M; i; --i) a[i] = a[i - 1]; a[0] = ' ';
    for(i = N; i; --i) b[i] = b[i - 1]; b[0] = ' ';

    makePrefix();

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

    printf("%d\n", n);
    for(i = 1; i <= minim(n, 1000); ++i)
        printf("%d", pos[i]);
    printf("\n");

    return 0;
}