#include<bits/stdc++.h>
using namespace std;
int power(int base , int expo)
{
if(expo ==0)
{
return 1;
}
if(expo == 1)
{
return base;
}
int x = power(base , expo/2);
if(expo%2 ==0)
{
return x*x;
}
else
{
return x*x*base;
}
}
int find_pattern(string pattern , string &s)
{
int pattern_hash =0;
int base =31;
int mod = 1e9 +7;
int cnt_occurances =0;
unordered_map<char, int>map;
map['w'] = 2;
map['b'] = 1;
for(int i =0 ; i < pattern.length(); i++)
{
int t = map[pattern[i]];
pattern_hash = (pattern_hash + t*power(base , i)) %mod;
}
int substring_hash = (map[s[0]]*power(base , 0) +map[s[1]]*power(base , 1) + map[s[2]]*power(base , 2 ))%mod;
if(substring_hash == pattern_hash)
{
cnt_occurances++;
}
for(int i =3 ; i < s.length() ; i++)
{
substring_hash = (substring_hash/base - map[s[i-2]] + map[s[i]]*power(base, 2)%mod)%mod;
if(substring_hash == pattern_hash)
{
cnt_occurances++;
}
}
return cnt_occurances;
}
bool solve(string &s)
{
int cnt_wendy = find_pattern("www", s);
int cnt_bob = find_pattern("bbb" , s );
return cnt_wendy > cnt_bob ? true : false;
}
int main()
{
string s = "wwwbbbww";
string p = solve(s) == true ? "wendy" : "bob";
cout << p;
} |
Comments
Post a Comment