Cod sursa(job #98194)

Utilizator DastasIonescu Vlad Dastas Data 10 noiembrie 2007 10:55:33
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Happy Coding 2007 Marime 0.98 kb
#include <cstdio>
#include <cstring>

const int maxn = 10000002;
const int maxl = 30;

FILE *in = fopen("abc2.in","r"), *out = fopen("abc2.out","w");

char a[maxn];
int p[maxn];

int n;
char c[maxl];

int getpref()
{
    p[1] = 0;

    int k = 0;
    int i;
    for ( i = 2; c[i]; ++i )
    {
        while ( k > 0 && c[k+1] != c[i] )
            k = p[k];

        if ( c[k+1] == c[i] )
            ++k;

        p[i] = k;
    }

    n = i-1;
}

char viz[maxn];
int main()
{
    fscanf(in, "%s", a+1);
    //getpref();

    int cnt = 0;
    while ( fscanf(in, "%s", c+1) == 1 )
    {
        int q = 0;
        getpref();

        for ( int i = 1; a[i]; ++i )
        {
            while ( q > 0 && c[q+1] != a[i] )
                q = p[q];
            if ( c[q+1] == a[i] )
                ++q;

            if ( q == n && !viz[i-n+1] )
                ++cnt, viz[i-n+1] = 1;
        }
    }

    fprintf(out, "%d\n", cnt);

	return 0;
}