C++のラップアラウンド文字列の一意のサブ文字列

これで、別の文字列pができました。私たちの仕事は、pの一意の空でない部分文字列がsにいくつ存在するかを調べることです。特に、入力は文字列pであり、文字列s内のpのさまざまな空でないサブ文字列の数を出力する必要があります。

したがって、入力が「zab」のような場合、出力は6になります。文字列「zab」の6つのサブ文字列「z」、「a」、「b」、「za」、「ab」、「zab」があります。文字列s

これを解決するには、次の手順に従います-

• サイズ26の配列dpを作成し、x：=0

  を設定します

• 0からpのサイズまでの範囲のIの場合

  • i> 0で（p [i] – p [i –1]が1またはp[i – 1] – p [i]が25）の場合、xを1増やします。それ以外の場合は、x：=1>

  • dp [p [i] –「a」のASCII]：=最大（x、dp [p [i] –「a」のASCII]）

• ret：=0

• 0から25の範囲のIの場合

  • ret：=ret + dp [i]

• retを返す

例（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