Cod sursa(job #329027)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 4 iulie 2009 14:42:42
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 kb
#include <stdio.h>   
#include <stdlib.h>   
#include <time.h>   
#include <string.h>   
#define S ((1<<20)-1)   
  
int V[S+10], Nr, ncol;   
unsigned int Val[S];   
char ss[10000002], ss2[50002];   
  
int main()   
{   
        int i, t, l, n, cst;   
        unsigned int p, pp, hash, val;   
  
        srand(time(0));   
  
        freopen("abc2.in", "r", stdin);   
        gets(ss);   
        n = strlen(ss);   
  
        cst = 'a';   
  
        while (scanf(" %s", ss2)==1)   
        {   
                l = strlen(ss2);   
                val = 0;   
                pp = 1;   
                for (i = 0; i < l; i++) val = val+(ss2[i]-cst)*pp, pp *= 3;   
                hash = val&S;   
                t = 0;   
                while ((V[hash]>0)&&(Val[hash]!=val)) hash = (hash+(++t))&S;   
                V[hash] = 1; Val[hash] = val;   
        }   
  
        cst = 'a';   
        val = 0; pp = 1;   
        for (i = 0; i < l; i++) val = val+(ss[i]-cst)*pp, pp *= 3;   
        p = pp/3;   
        hash = val&S; Nr+=V[hash];   
  
        for (i = l; i <= n; i++)   
        {   
                val = (val/3)+(ss[i]-cst)*p;   
                hash = val&S;   
                for (t=0; ((V[hash]>0)&&(Val[hash]!=val)) ;hash = (hash+(++t))&S);   
                Nr += V[hash];   
        }   
  
        freopen("abc2.out", "w", stdout);   
        printf("%d\n", Nr);   
  
        return 0;   
           
}