hackerrank-1/beautiful binary string.cpp at master · HarshalPamecha/hackerrank-1 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

#define PRIME 3

int calculateHash(string str,int len)
{
    long long res=0;
    for(int i=0;i<len;i++)
    {
        res+=str[i]*pow(PRIME,i);
    }

    return res;
}

int calculate(string str,int len)
{
    string pattern="010";
    long long tHash=calculateHash(str,3);
    long long pHash=calculateHash(pattern,3);

    int count=0;
   // cout<<pHash<<endl;
    for(int i=0;i<len-3+1;)
    {
        bool change=false;
        //cout<<i<<" "<<tHash<<endl;
        if(tHash == pHash)
        {
            //check if the strings match
            bool flag=true;
            for(int i1=0;i1<3;i1++)
            {
                if(pattern[i1] != str[i+i1])
                {
                    flag=false;
                    break;
                }
            }
            if(flag)
            {
                i=i+3;
                count++;
                change=true;
            }
        }

        //recalculating the hash
        if(change)
        {
            if(i<len-2)
            {
                tHash=0;
                int x=i;
                for(int j=0;j<3;j++)
                {
                    tHash+=str[x]*pow(PRIME,j);
                    x++;
                }
            }
        }
        else
        {
            tHash-=str[i];
            tHash/=3;
            tHash+=str[i+3]*pow(PRIME,2);
            i++;
        }


    }

    return count;

}

int main(){
    int n;
    cin >> n;
    string B;
    cin >> B;
    cout<<calculate(B,n);
    return 0;
}