問題概要

"110" という文字列を 10000000000 個連結してできる文字列を $S$ とする。

長さ $N$ の文字列 $T$ が与えられる。 $S$ の中に $T$ が連続する部分文字列としていくつ含まれるかを求めよ。

制約

$1 \le N \le 2 \times 10^{5}$

考えたこと

こういう、端の処理が慎重を要するタイプの問題、実はめっちゃ苦手なのです...

とりあえず $V = 10000000000$ とする。 $T$ は左右両端の端の部分を除くと "110" の繰り返しになっていなければならない。僕は両端から削る方針でやった。

まずは次の処理をする。

T = "1" は例外的、答えは $2V$ となる
T = "0", "11" の場合は、答えは $V$ となる
T の最初の 1 文字が "0" の場合は、それを除去して、 $S$ からも最初の "110" を除去する ( $V$ をデクリメントする)。
T の最初の 2 文字が "10" の場合は、それを除去して、 $S$ からも最初の "110" を除去する ( $V$ をデクリメントする)。

そうすると、 $T$ は "110110...110" という形になるはず ( = "", "1", "11")。ならなければ答えは 0。そして末尾の * が空文字でないならば、それを除去して、 $S$ からも最後の "110" を除去する ( $V$ をデクリメントする)。

この段階で $T$ の "110" の繰り返し数を $a$ としたとき、答えは $V-a+1$ となる ( $a = 1$ のとき $V$ 個になることを想像するとわかりやすい)。

計算量は $O(N)$ 。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string T;
    cin >> N >> T;
    auto solve = [&]() -> long long {
        long long V = 10000000000LL;
        if (T == "0") return V;
        else if (T == "1") return V * 2;

        if (T.size() >= 1 && T.substr(0, 1) == "0") T = T.substr(1), --V;
        else if (T.size() >= 2 && T.substr(0, 2) == "10") T = T.substr(2), --V;
        if (T.size() % 3 == 1) {
            if (T.substr(T.size()-1) != "1") return 0;
            T = T.substr(0, T.size()-1);
            --V;
        }
        else if (T.size() % 3 == 2) {
            if (T.substr(T.size()-2) != "11") return 0;
            T = T.substr(0, T.size()-2);
            --V;
        }
        for (int i = 0; i < T.size(); i += 3) if (T.substr(i, 3) != "110") return 0;
        return V - T.size()/3 + 1;
    };
    cout << solve() << endl;
}

別解：開始位置を全探索

もう少し明快なロジックがありそう。 $S$ は周期 3 なので、 $S$ における $T$ の開始位置を 3 通り全探索してしまうという考え方もできる。if 文で書くより for 文を回して探索できるなら、そっちの方がいい。

$S$ の 0 文字目、1 文字目、2 文字目からマッチングさせていって、もしマッチするならば、 $S$ 中の費やした "110" のブロック数を $a$ とすると、

result += V - a + 1;

というように、答えに加算していけばよい。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S = "110", T;
    cin >> N >> T;
    auto solve = [&]() -> long long {
        long long V = 10000000000LL;
        if (T == "0") return V;
        else if (T == "1") return V * 2;

        long long res = 0;
        for (int i = 0; i < 3; ++i) {
            long long a = (T.size() + i + 2) / 3;
            long long add = V - a + 1;

            bool ok = true;
            for (int j = 0; j < T.size(); ++j) {
                if (T[j] != S[(j+i)%3]) ok = false;
            }
            if (ok) res += add;
        }
        return res;
    };
    cout << solve() << endl;
}