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
热门推荐
10 高考前祝福语简短字句
11 异性朋友简短生日祝福语
12 低调祝福语简短10字
13 成长仪式的简短祝福语
14 酒桌升学祝福语简短
15 八十大寿简短祝福语
16 传统新婚祝福语创意简短
17 短祝福语简短暖心
18 新婚贺词简短的祝福语