Cod sursa(job #2291373)

Utilizator LucianTLucian Trepteanu LucianT Data 27 noiembrie 2018 22:05:58
Problema Abc2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.32 kb
#include <fstream>
#include <vector>
#include <cstring>
using namespace std;

const int maxLen=1e7+2;
const int maxWord=22;
const int MOD=24593;

char text[maxLen];
char word[maxWord];
int textLen;
int wordLen;
int sol;

vector<unsigned int> hashT[MOD];

inline void insertHash(unsigned int x){
    int where=x%MOD;
    hashT[where].push_back(x);
}

bool findHash(unsigned int x){
    int where=x%MOD;

    for(int i=0;i<(int)hashT[where].size();i++)
        if(hashT[where][i]==x)
            return true;
    return false;
}

int main(){
    ifstream cin("abc2.in");
    ofstream cout("abc2.out");

    cin>>text;
    textLen=strlen(text);

    while(cin>>word){
        wordLen=strlen(word);
        unsigned int hashed=0;

        for(int i=0;i<wordLen;i++)
            hashed=hashed*3+(word[i]-'a');

        insertHash(hashed);
    }

    unsigned int power=1;
    for(int i=1;i<wordLen;i++)
        power=3*power;

    unsigned int currHash=0;
    for(int i=0;i<wordLen;i++)
        currHash=currHash*3+text[i]-'a';

    if(findHash(currHash))
        sol++;

    for(int i=wordLen;i<textLen;i++){
        currHash-=(text[i-wordLen]-'a')*power;
        currHash=currHash*3+text[i]-'a';

        if(findHash(currHash))
            sol++;
    }

    cout<<sol;

    return 0;
}