C++在具有位置说明的字符串中查找不重叠的子字符串

Question

我正试图找出如何在字符串中找到不重叠的子字符串的计数，但只能找到那些距离相同的子字符串。我设法得到了一些不重叠的子字符串，但这只是需求的子集。

示例：我有一根绳子"aaaaaaaaaa"；并且我想要计数非重叠子串的数目"；aa"；但仅限于距离乘以2的那些。

标准的非重叠代码返回8，这是正确的(aa aa aa aa b aa aa ba-用空格区分结果(。它在位置0,2,4,6,8,11,13,15找到子串。

当我尝试执行距离要求时，我遇到了一个问题。所需计数应为7，省略位置11处的"a"，并在位置12处继续(aa aa aa aa ba aa ab a(。。。再次用空格来区分这些发现，位置11处的"a"应该与位置10处的"b"形成子串"ba">

我试图使用模来识别正确的位置，并只计算从模结果为0的位置开始的子字符串，但通过执行我的代码，处理仅在第5次出现时停止，在中间的"b"之前，忽略接下来的子字符串。

wrong: aa aa aa aa aa b aa aa aa b a
good:  aa aa aa aa aa ba aa aa ab a

类似地，它应该与其他大小一起工作，例如，查找"0"；aaa"；，因此结果将是4〃；aaaaaaaaa-aba aaaab-a"而不是5〃；aaaaaaaaab aaaaba">

string str = "aaaaaaaaaabaaaaaaba";
string sub = "aa";
int count = 0;
for (size_t offset = str.find(sub); offset != std::string::npos;
offset = str.find(sub, offset + sub.length()))
{
int pos = offset % sub.length();
if (pos == 0)
{
++count;
cout << "offset: " << offset << " count: " << count << endl;
}
}
cout << "count: " << count << endl;
return 0;

Answer 1

您的循环做了一件错误的事情：它试图从最后找到的偏移量+2(aa的长度(开始find子字符串。

在奇数位置找到第一个aa之后，所有后续尝试也将找到奇数位置。

这项工作：

for (size_t offset = str.find(sub); offset != std::string::npos;
offset = str.find(sub, offset + 1))

Answer 2

我建议只使用std::string::find来找到第一个子字符串，然后每次迭代只执行sub.size()。

以下是在str:中的当前子字符串上使用std::string_view的示例

#include <string>
#include <string_view>
#include <iostream>
int main() {
std::string str = "aaaaaaaaaabaaaaaaba";
//                 ! ! ! ! ! X ! ! X X
//                 0 2 4 6 81012141618
std::string sub = "aa";
int count = 0;
for(size_t offset = str.find(sub);
offset < str.size() - sub.size();
offset += sub.size())             // just step sub.size() here
{
if(sub == std::string_view(str.c_str() + offset, sub.size()))
std::cout << "offset: " << offset << " count: " << ++count << 'n';
}
std::cout << "count: " << count << 'n';
}

输出：

offset: 0 count: 1
offset: 2 count: 2
offset: 4 count: 3
offset: 6 count: 4
offset: 8 count: 5
offset: 12 count: 6
offset: 14 count: 7
count: 7

Answer 3

我一整天都在努力寻找解决方案，在发布问题几分钟后，我找到了解决方案(墨菲定律(。

诀窍是添加一个"else"语句，并将偏移量移回模余数：

if (pos == 0)
{
++count;
cout << "offset: " << offset << " count: " << count << endl;
}
else
{
offset = offset - pos;
cout << "pos: " << pos << endl;
}