Cod sursa(job #1518592)

Utilizator antanaAntonia Boca antana Data 5 noiembrie 2015 23:48:32
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<string.h>
using namespace std;
char t[10000001], s[21];
long long aux[50001], nr, v[50001];
int ap[50001],a, b;
int k=-1, n;
int cautbinar(int x)
{
    int l1, l2, m;
    l1=1;
    l2=b;
    while(l1<=l2)
    {
        m=(l1+l2)/2;
        if(v[m]>x)
            l2=m-1;
        if(v[m]<x)
            l1=m+1;
        if(v[m]==x)
        {
            return 1;
        }
    }
    return 0;
}
int main()
{
    freopen("abc2.in", "r", stdin);
    freopen("abc2.out", "w", stdout);
    int i, cate=0,stop=0, f=1;;
    char c;
    scanf("%c", &c);
    while(c!='\n'){
        t[++k]=c;
        scanf("%c", &c);
    }
    gets(s);
    n=strlen(s);
    while(stop==0){
        nr=0;
        for(i=0;i<n;i++){
            nr=(nr*4)+s[i]-'a'+1;
        }
        aux[++a]=nr;
        gets(s);
        if(s[0]==NULL)
            stop=1;
    }
    sort(aux+1, aux+a+1);
    int secv=1;
    for(i=2;i<=a+1;i++)
    {
        if(aux[i]!=aux[i-1])
        {
            ap[++b]=secv;
            secv=1;
            v[b]=aux[i-1];

        }
        else
            secv++;
    }
    //cautare binara
    if(n>k)
        printf("0");
    else{
        nr=0;
        for(i=0;i<n;i++){
            nr=(nr*4)+t[i]-'a'+1;
            if(i!=0)
                f*=4;
        }
        cate+=cautbinar(nr);
        for(i=n;i<k;i++)
        {
            nr-=(t[i-n]-'a'+1)*f;
            nr*=4;
            nr+=t[i]-'a'+1;
            cate+=cautbinar(nr);
        }
    }
    printf("%d", cate);

    return 0;
}