C ++中的环绕字符串中的唯一子字符串
假设字符串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"));
}输入值
"zab"
输出结果
6