Cod sursa(job #1129451)

Utilizator vlad96Vlad Zuga vlad96 Data 27 februarie 2014 22:18:36
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <stdio.h>
#include <string.h>

using namespace std;

const int N = 200002;
char a[N], b[N];
int pi[N], poz[1024];
int n, m, q, nr;

void read ()
{
    FILE *fis = fopen ("strmatch.in", "r");
    fgets(a, N, fis);
    fgets(b, N, fis);
    n = strlen(a) - 1;
    m = strlen(b) - 1;
    for (int i = n; i >= 1; i -- )
        a[i] = a[i-1];
    for (int i = m; i >= 1; i -- )
        b[i] = b[i-1];
    a[0] = b[0] = ' ';
    fclose(fis);
}

inline int minim (int a, int b)
{
    if ( a < b )
        return a;
    return b;
}

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

void solve ()
{
    prefix();
    q = 0, nr = 0;
    for (int i = 1; i <= m; i ++ )
    {
        while ( q && a[q+1] != b[i] )
            q = pi[q];
        if ( a[q+1] == b[i] )
            ++ q;
        if ( q == n )
        {
            q = pi[n];
            ++ nr;
            if ( nr <= 1000 )
                poz[nr] = i-n;
        }
    }
}

void write ()
{
    FILE *fis2 = fopen ("strmatch.out", "w");
    fprintf(fis2, "%d\n", nr);
    for (int i = 1; i <= minim(nr, 1000); i ++ )
        fprintf(fis2, "%d ", poz[i]);
    fclose(fis2);
}

int main()
{
    read();
    solve();
    write();
    return 0;
}