문자열 해싱 (String Hashing)

map사용 없이 문자열 직접 해싱해서 사용

long long hash(string s){
    const int p = 53;
    const int m = 1e9 + 9; //10^9 + 9

    int hash_val = 0;
    int pow_p = 1;

    for(int i = 0; i < s.length(); i++){
        hash_val = (hash_val + (s[i] - 'a' + 1) * pow_p) % m;
        pow_p = (p * pow_p) % m;
    }
    return hash_val;
}