Cod sursa(job #173344)

Utilizator savimSerban Andrei Stan savim Data 7 aprilie 2008 17:46:07
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>

using namespace std;

#define maxl 50010
#define ltext 1000010
#define prim 666013

char text[ltext];
char cuv[maxl][25];
int p[maxl],l[maxl],fol[maxl];
int nr[25];
int i,j,n,m,lung,nrcuv;
unsigned int k,put;
vector <unsigned int> hash[prim+10];

int comp(int x, int y)
{
    return l[x]<l[y];    
}

inline int apartine(unsigned int k)
{
       int rest=k%prim,l=hash[rest].size(),i;
       
       for (i=0; i<=l-1; i++)
           if (hash[rest][i]==k) return 1;
           
       return 0;
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);
    
    scanf("%s",text+1);
    text[0]=' ';
    m=strlen(text)-1;
    
    n=0;nrcuv=0;
    while (!feof(stdin))
    {
       n++;
       scanf("%s",cuv[n]+1);
       cuv[n][0]=' ';
       l[n]=strlen(cuv[n])-1;
       p[n]=n;
       nr[l[n]]++;
    }
    p[n]=0;n--;
    
    sort(p+1,p+n+1,comp);
    
    for (i=1; i<=n && l[p[i]]<=m;)
    {
        for (j=0; j<prim; j++) 
            vector <unsigned int> ().swap(hash[j]);
        
        for (lung=l[p[i]]; i<=n && lung==l[p[i]]; i++)
        {
             k=0;
             for (j=1; j<=l[p[i]]; j++) 
                 k=k*3+cuv[p[i]][j]-'a';
             hash[k%prim].push_back(k);
        }
        
        put=1;k=0;
        for (j=1; j<=lung; j++)
        {
            k=k*3+text[j]-'a';
            if (j>1) put*=3;
        }
        for (j=1; j<=m+1; j++)
            fol[j]=0;

        text[m+1]='a';
        for (j=lung+1; j<=m+1; j++)
        {
            if (!fol[j-lung] && apartine(k))
            {
               nrcuv++;
               fol[j-lung]=1;
            }

            k=k-put*(text[j-lung]-'a');
            k=k*3+text[j]-'a';
        }
    }

    printf("%d\n",nrcuv);
    
    return 0;    
}