playground/leetcode/maximum-repeating-substring/maximum-repeating-substring.cpp at main · MuhtasimTanmoy/playground · 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
// class Solution {
// public:
//     int maxRepeating(string sequence, string word) {
//         int q = 1e9 + 1;
//         int p = 31;

//         vector<long long> hash(max(size(sequence), size(word)));
//         hash[0] = 1;
//         for ( int i = 1; i < size(hash); i++)
//             hash[i] = ( hash[i-1] * p ) % q;

//         // for(int i = 0; i < size(hash); i++)
//         //     cout<<hash[i]<<endl;
//         // cout<<endl;

//         long long wordHash = 0;
//         for(int i = 0; i < size(word); i++)
//             wordHash = (wordHash + ( word[i] - 'a' + 1) * hash[i]) % q;

//         // cout<<wordHash<<endl;
//         // cout<<endl;

//         vector<long long> longHash(size(sequence) + 1, 0);
//         for(int i = 0; i < size(sequence); i++)
//             longHash[i + 1] = (longHash[i] + (sequence[i] - 'a' + 1) * hash[i]) % q;

//         // for(int i = 0; i < size(longHash); i++)
//         //     cout<<longHash[i]<<endl;
//         // cout<<endl;

//         int result = 0;
//         int count = 0;
//         for (int i = 0; i + size(word) - 1 < size(sequence); ) {
//             int currentHash = ( longHash[i + size(word)] + q - longHash[i] ) % q;
//             // cout<<currentHash<<endl;
//             if (currentHash == ( ( wordHash * hash[i]) % q) ) {
//                 // cout<<"Found: "<<i<<endl;
//                 i += size(word);
//                 count++;
//                 result = max(result, count);
//             } else {
//                 i++;
//                 count = 0;
//             }
//         }

//         return result;
//     }
// };

class Solution {
public:
    int maxRepeating(string sequence, string word) {
        int cnt = 0;
        string tmp = word;
        while (sequence.find(tmp) != string::npos) {
            ++cnt;
            tmp += word;
        }
        return cnt;
    }
};