C++で繰り返しパターンを数える：周期検出による効率的な解法

問題概要

空でない2つの文字列 s1・s2(それぞれ最大100文字)と、0以上10⁶以下の範囲にある2つの整数 n1・n2 が与えられます。

ここで S1 = [s1, n1]、S2 = [s2, n2] とおきます。S = [s, n] は「文字列 s を n 個連結した文字列」を表します。たとえば ["ab", 4] は "abababab" です。

さらに、文字列 s2 からいくつかの文字を取り除くことで s1 が得られるとき、「s1 は s2 から取得できる」と定義します。この定義では、"abc" は "abdbec" から取得できますが、"acbbe" からは取得できません。

目的は、[S2, M] が S1 から取得できるような最大の整数 M を求めることです。

入出力の例

s1 = "acb"、n1 = 4、s2 = "ab"、n2 = 2 が入力された場合、答えは 2 になります。

実際に確認してみましょう。S1 = "acbacbacbacb"("acb" を4回連結)からは、"abab"("ab" を2回連結したもの)を2回分だけ部分列として取り出せます。3回目以降は文字が足りず不可能なため、最大値は 2 となります。

解法の考え方

単純に1文字ずつ照合していくと、n1 や n2 が最大 10⁶ に達するため計算量が膨大になります。そこで鍵となるのが、周期性(サイクル)を検出して残りを一括でスキップするという発想です。

具体的な手順は次のとおりです。

1. 事前チェック： s2 の各文字 c について、c が s1 に1つも含まれていなければ、答えは必ず 0 になるため即座に 0 を返します。
2. ポインタの初期化： p1 := 0(s1 側の位置)、p2 := 0(s2 側の位置)、mark := 0(周期検出用の記録)とします。
3. シミュレーション： p1 < s1の長さ × n1 の間、以下を繰り返します。
   • c := s2[p2 mod s2の長さ] として、次にマッチさせるべき文字を決めます。
   • s1[p1 mod s1の長さ] ≠ c である限り p1 を進めます。
   • p2 と p1 をそれぞれ1つ進めます。
   • p2 mod s2の長さ == 0(s2 をちょうど一周した)とき:
     • 最初の一周であれば(p2 == s2の長さ)、その時点の p1 を mark に記録します。
     • それ以外で p1 mod s1の長さ == mark mod s1の長さ が成り立てば周期が検出されたので、残りの範囲をまとめて処理します:
       • round := (s1の長さ × n1 − p1) / (p1 − mark)
       • p1 += round × (p1 − mark)
       • p2 += round × (p2 − s2の長さ)
4. 結果の算出： 最後に p2 / s2の長さ / n2 を返します。これは S2 全体([s2, n2])が何セット分取り出せるかを表します。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int getMaxRepetitions(string s1, int n1, string s2, int n2) {
      for (auto c : s2) {
         if (s1.find(c) == string::npos)
            return 0;
      }
      int p1 = 0, p2 = 0, mark = 0;
      while (p1 < s1.length() * n1) {
         char c = s2[p2 % s2.length()];
         while (s1[p1 % s1.length()] != c && p1 <s1.length() * n1)
         p1++;
         p2++;
         p1++;
         if (p2 % s2.length() == 0) {
            if (p2 == s2.length()) {
               mark = p1;
            }
            else if (p1 % s1.length() == mark % s1.length()) {
               int round = (s1.length() * n1 - p1) / (p1 - mark);
               p1 += round * (p1 - mark);
               p2 += round * (p2 - s2.length());
            }
         }
      }
      return p2 / s2.length() / n2;
   }
};
main() {
   Solution ob;
   cout << (ob.getMaxRepetitions("acb",4,"ab",2));
}

入力

"acb",4,"ab",2

出力

2

まとめ

この問題は、素朴なシミュレーションでは間に合わないほど大きな n1・n2 が前提となっています。s1 上の走査位置が過去に記録した地点と同じ状態に戻った瞬間を捉え、その周期を使って残りの繰り返しを一括計算することで、大幅な高速化を実現できるのがこの解法のポイントです。事前に s2 の文字がすべて s1 に含まれるかを確認しておくことで、答えが 0 になるケースも素早く判定できます。