Cod sursa(job #101663)

Utilizator fireatmyselfBogdan-Alexandru Stoica fireatmyself Data 13 noiembrie 2007 18:34:07
Problema Abc2 Scor 0
Compilator c Status done
Runda Happy Coding 2007 Marime 1.3 kb
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define S ((1<<23)-1)

int V[S+10], Nr;
char ss[10000002], ss2[50002];

int main()
{
        int i, j, l, n;
        long long hash, x, y;

        srand(time(0));
        y = 1000000000+(2*rand()%1000000001)-1;

        freopen("abc2.in", "r", stdin);
        gets(ss);
        n = strlen(ss);
        scanf(" ");
        gets(ss2);
        l = strlen(ss2);
        n = n-l;

        for (i = 0; i <= n; i++)
        {
            hash = y;
            for (j = 0; j < l; j++)
            {
                x = (hash*y);
                hash = (hash+x+ss[i+j])&S;
            }
            V[hash]++;
        }

        hash = y;
        for (j = 0; j < l; j++)
        {
            x = (hash*y);
            hash = (hash+ss2[j]+x)&S;
        }
        Nr += V[hash];
        V[hash] = 0;

        while (scanf(" %s", ss2)!=EOF)
        {
                hash = y;
                for (j = 0; j < l; j++)
                {
                    x = (hash*y);
                    hash = (hash+ss2[j]+x)&S;
                }
                Nr += V[hash];
                V[hash] = 0;
        }

        freopen("abc2.out", "w", stdout);
        printf("%d\n", Nr);

        return 0;
        
}