Cod sursa(job #1654310)

Utilizator CalarisPredut Denis Stefanita Calaris Data 16 martie 2016 22:32:22
Problema Abc2 Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <vector>
#include <string.h>

using namespace std;

const int MAX = 102931;

vector<unsigned int> hashTable[MAX+70];
int length=0;
long long power[21];
int ans = 0;

vector<unsigned int>::iterator operation_search(unsigned int number,unsigned int index)
{
    vector<unsigned int>::iterator it;

    for(it = hashTable[index].begin(); it != hashTable[index].end(); ++it)
        if (*it == number)
            return it;

    return hashTable[index].end();
}

void operation_add(string word)
{
    int i;
    unsigned int index = 0;
    for(i=0;i<length;++i)
        index=(index*3)+(word[i]-'a');

     if(operation_search(index,index%MAX)==hashTable[index%MAX].end())
        hashTable[index%MAX].push_back(index);
}

int main()
{
    fstream f("abc2.in",ios::in);
    ofstream g("abc2.out");

    string text,word;
    int length2,i;
    unsigned int index=0;
    f>>text;

    power[0]=1;

    while(f>>word)
        {
        if(!length)length=word.length();
        operation_add(word);
        }

    length2=text.length();

    for(i=1;i<=length;++i)
        power[i]=power[i-1]*3;

    for(i=0;i<length;++i)
        index=(index*3)+(text[i]-'a');

    if(operation_search(index,index%MAX)!=hashTable[index%MAX].end())
                ++ans;

    for(i=length;i<length2;++i)
        {
         index = index - power[length-1]*(text[i-length]-'a');
         index = (index*3)+(text[i]-'a');

         if(operation_search(index,index%MAX)!=hashTable[index%MAX].end())
                ++ans;
        }

    g<<ans;
    return 0;
}