Cod sursa(job #1003821)

Utilizator andrettiAndretti Naiden andretti Data 1 octombrie 2013 17:53:14
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#define pb push_back
#define maxn 10000005
#define maxm 25
#define MOD 666013
using namespace std;
typedef unsigned int ui;

int n,m,sol;
char t[maxn],s[maxm];
vector <ui> l[MOD];

int hash_key(ui k){
    return k%MOD;
}

void insert(ui val)
{
    int k=hash_key(val);
    l[k].pb(val);
}

int search(ui val)
{
    int k=hash_key(val);
    for(unsigned int i=0;i<l[k].size();i++)
     if(l[k][i]==val) return 1;
    return 0;
}

void read()
{
    ui nr,f;

    scanf("%s\n",t+1);
    n=strlen(t+1);
    while(!feof(stdin))
    {
        scanf("%s\n",s+1);
        m=strlen(s+1); nr=0; f=1;
        for(int i=m;i;i--)
         nr+=(s[i]-'a')*f,f*=3;
        insert(nr);
    }
}

void solve()
{
    ui nr=0,f=1;

    if(m>n) {sol=0; return;}
    for(int i=m;i;i--)
     nr+=(t[i]-'a')*f,f*=3;
    if(search(nr)) sol++;
    f/=3;

    for(int i=m+1;i<=n;i++)
    {
        nr-=(t[i-m]-'a')*f;
        nr*=3; nr+=t[i]-'a';
        if(search(nr)) sol++;
    }
}

int main()
{
    freopen("abc2.in","r",stdin);
    freopen("abc2.out","w",stdout);

    read();
    solve();
    printf("%d",sol);

    fclose(stdin);
    fclose(stdout);
    return 0;
}