C ++中的环绕字符串中的唯一子字符串

Z时代
2024-01-10
分类：综合

假设字符串s是“ abcdefghijklmnopqrstuvwxyz”的无限环绕字符串，因此值s看起来像这样-“ ... zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd ....”。

现在我们有了另一个字符串p。我们的工作是找出s中存在多少个p的唯一非空子字符串。特别地，我们的输入是字符串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的范围

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"));
}