Cod sursa(job #1489470)

Utilizator dorumusuroiFMI - Doru Musuroi dorumusuroi Data 21 septembrie 2015 10:36:15
Problema Abc2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <bits/stdc++.h>

using namespace std;

const char iname[] = "abc2.in";
const char oname[] = "abc2.out";
const unsigned int MOD = 666013, BASE = 3;
int n = 0, lenght, textLenght, wordLenght, ans;
char text[10000100], word[25];
vector<unsigned int> H[MOD];

unsigned int pow3(int p){
    unsigned int rez = 1, val = BASE;
    while(p != 0){
        if(p & 1) rez *= val;
        val *= val;
        p >>= 1;
    }
    return rez;
}


bool SearchHash(unsigned int val){
    int poz = val % MOD;
    for(auto it = H[poz].begin(); it != H[poz].end(); ++it)
        if(*it == val)
            return true;
    return false;
}

void read(){
    freopen(iname, "r", stdin);
    scanf("%s", text);
    while(scanf("%s", word) == 1){
        if(word[0] != '\n'){
            wordLenght = strlen(word);
            unsigned int reprez = 0;
            for(int i = 0; i < wordLenght; ++i)  reprez = reprez * BASE + (word[i] - 'a');
            if(!SearchHash(reprez))
                H[reprez%MOD].push_back(reprez);
        }
    }
}

int main(){
    read();
    textLenght = strlen(text);
    unsigned int reprez = 0;
    if(wordLenght <= textLenght)
    for(int i = 0; i < wordLenght; ++i){
        reprez = reprez * BASE + (text[i]-'a');
    }
    if(SearchHash(reprez)) ++ans;
    for(int i = wordLenght; i < textLenght; ++i){
        reprez = reprez - pow3(wordLenght-1)*((unsigned int)(text[i-wordLenght] - 'a'));
        reprez = reprez * BASE + ((unsigned int)(text[i] - 'a'));
        if(SearchHash(reprez)) ++ans;
    }
    freopen(oname,"w", stdout);
    printf("%d", ans);
    return 0;
}