Cod sursa(job #2291361)

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

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

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

vector<unsigned int> hashT[MOD];

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+1);
    textLen=strlen(text+1);

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

        for(int i=1;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=1;i<=wordLen;i++)
        currHash=currHash*3+text[i]-'a';

    if(findHash(currHash))
        sol++;

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

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

    cout<<sol;

    return 0;
}