Cod sursa(job #2291297)

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

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

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

vector<int> hashT[MOD];

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

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

    for(auto it:hashT[where])
        if(it==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);
        int hashed=0;

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

        insertHash(hashed);
    }

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

    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;
}