C++で解く！ラップアラウンド文字列に含まれる一意な部分文字列の数

問題の概要

「abcdefghijklmnopqrstuvwxyz」というアルファベット順の文字列を無限に循環させた文字列 s を考えます。このとき s は次のような形になります。

「...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....」

ここで、別の文字列 p が与えられます。私たちの課題は、p の空でない部分文字列のうち、s に含まれるものが全部で何種類あるかを求めることです。つまり、入力として文字列 p を受け取り、s 内に存在する p の異なる非空部分文字列の個数を出力します。

例えば、入力が「zab」の場合、出力は 6 になります。これは「z」「a」「b」「za」「ab」「zab」の6つの部分文字列が、いずれも文字列 s の中に存在するためです。

解法のアプローチ

この問題は、動的計画法（DP）を使うことで効率的に解けます。手順は以下の通りです。

• サイズ26の配列 dp を作成し、変数 x を 0 で初期化します。
• i を 0 から p の長さまでループします。
  • i > 0 かつ（p[i] − p[i−1] が 1、または p[i−1] − p[i] が 25）という条件を満たす場合は x を 1 増やします。これは隣接する2文字がアルファベット順に連続している、あるいは z から a へ折り返していることを意味します。条件を満たさない場合は x を 1 にリセットします。
  • dp[p[i] − 'a'] に、x と現在の値のうち大きい方を代入します。
• ret を 0 で初期化します。
• i を 0 から 25 までループして、ret に dp[i] を順に加算していきます。
• 最後に ret を返します。

なぜこの方法で正しく数えられるのか

ポイントは「各文字について、その文字で終わる最長の連続アルファベット列の長さを記録する」ことです。ラップアラウンド文字列では、開始文字と長さが決まれば部分文字列は一意に定まるため、文字ごとの最長長さの総和がそのまま答えになります。また、同じ部分文字列が複数回現れても、max を取ることで二重カウントを確実に防げます。

C++での実装例

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int findSubstringInWraproundString(string p) {
      vector <int> dp(26);
      int x = 0;
      for(int i = 0; i < p.size(); i++){
         if(i > 0 && (p[i] - p[i - 1] == 1 || p[i - 1] - p[i] == 25)){
            x++;
         }
         else x = 1;
         dp[p[i] - 'a'] = max(x, dp[p[i] - 'a']);
      }
      int ret = 0;
      for(int i = 0; i < 26; i++){
         ret += dp[i];
      }
      return ret;
  }
};
main(){
   Solution ob;
   cout << (ob.findSubstringInWraproundString("zab"));
}

入力

"zab"

出力

6

計算量の評価

時間計算量は O(n)（n は文字列 p の長さ）であり、空間計算量はサイズ26の固定配列しか使わないため O(1) です。非常に効率的な解法と言えます。