C++で大きな数値に含まれる3桁の繰り返し数列をすべて検出・表示する方法

この問題では、1つの数値が与えられ、その中に出現する3桁の繰り返し数列をすべて出力することが求められます。

まず、例を見て問題を理解しましょう。

入力: 98769876598765
出力:
    987: 3回
    876: 3回
    765: 2回

この問題を解くには、非常に大きな数値を文字列として格納して扱います。数値の各桁は文字として処理されます。まず最初の3桁をチェックし、その後、インデックス3から末尾まで順に走査しながら、スライドウィンドウ方式で新たな3桁の数を取得していきます。各3桁の数の出現頻度をカウントし、最後に頻度が1を超える（2回以上出現する）3桁の数をすべて出力します。

実装例

以下のコードは、この解法を実装したものです。

#include <bits/stdc++.h>
using namespace std;
void printRepeatingNumber(string s) {
    int i = 0, j = 0, val = 0;
    map <int, int> threeDigitNumber;
    val = (s[0] - '0') * 100 + (s[1] - '0') * 10 + (s[2] - '0');
    threeDigitNumber[val] = 1;
    for (i = 3; i < s.length(); i++) {
        val = (val % 100) * 10 + s[i] - '0';
        if (threeDigitNumber.find(val) != threeDigitNumber.end()) {
            threeDigitNumber[val] = threeDigitNumber[val] + 1;
        } else {
            threeDigitNumber[val] = 1;
        }
    }
    for (auto number : threeDigitNumber) {
        int key = number.first;
        int value = number.second;
        if (value > 1)
            cout<<key<<": "<<value<<" times\n";
    }
}
int main() {
    string num = "98769876598765";
    cout<<"All 3 digit repeating numbers are :\n";
    printRepeatingNumber(num);
}

出力結果

All 3 digit repeating numbers are −
765: 2 times
876: 3 times
987: 3 times