仅对字符串进行基本操作时，子字符串在字符串中连续出现的次数

Question

int longest_str(std::string str, std::string dna) {
int longest_count = 0;
int current_count = 0;
std::string temp;
for (int i = 0; i <= (dna.size() - str.size()); ++i) {
if (dna.at(i) == str.at(0)) {

for (int j = i; j < i + str.size(); ++j) {
temp.push_back(dna.at(j));
}
if (temp.compare(str) == 0) {
current_count++;
temp.clear();
i += str.size();

} else if (temp.compare(str) != 0) {
if (current_count >= longest_count) {
longest_count = current_count;
}
temp.clear();
current_count = 0;

} 
} else if (dna.at(i) != str.at(0)) {
if (current_count >= longest_count) {
longest_count = current_count;
}
continue;
}

}

return longest_count;
}

基本上我在这里要做的是循环通过给定的DNA链，当我遇到STR的第一个字母，说在索引I，我将追加下一个I + STR .size()字母从DNA链到一个临时变量。然后，将该临时变量与STR进行比较，如果它们相等，则将当前计数增加1，清除临时字符串，相应增加索引，并重复该过程。如果临时字符串不等于STR，我将清除字符串，更新到该点的最长计数，并将当前计数重置为0。如果遇到不等于STR第一个字符的字符，我将类似地更新最长计数，将当前计数重置为0，并重复此过程。

例如，如果给定的DNA是"GTATTAATTAATTAATTAGTA"， STR是"ATTA"，这个函数应该返回4。

函数已经给我看似随意的回答我在测试时对不同输入,所以我不确定发生了什么错误。我的猜测是我更新longest_count变量的方式有问题。有什么建议吗?

Answer 1

问题是你这样做了:

i += str.size()

但是你忘记了你的循环本身也在增加i，所以你实际上跳过了一个索引。

第二个问题是你可能在 之前退出循环

if (current_count >= longest_count) {
longest_count = current_count;
}

如果最后一次匹配小于返回字符串的长度(或者最后一次匹配正好在字符串的末尾结束)，则执行。

这是你的代码的脏修复:

int longest_str(std::string str, std::string dna) {
int longest_count = 0;
int current_count = 0;
std::string temp;
for (int i = 0; i <= (dna.size() - str.size()); ++i) {
if (dna.at(i) == str.at(0)) {

for (int j = i; j < i + str.size(); ++j) {
temp.push_back(dna.at(j));
}

if (temp.compare(str) == 0) {
current_count++;
temp.clear();
i += (str.size()-1);
} else if (temp.compare(str) != 0) {
temp.clear();
current_count = 0;
}
if (current_count >= longest_count) {
longest_count = current_count;
}
} else if (dna.at(i) != str.at(0)) {
if (current_count >= longest_count) {
longest_count = current_count;
}
continue;
}

}

return longest_count;
}

其他解决方案可能更简洁，但希望你现在能看到问题所在。

您可能错过的另一个问题是当字符串包含重叠匹配时会发生什么。例如:

"ATTATTAATTA">

在你的代码中，你会发现第一个"ATTA"，但你不会发现重叠的"ATTA"，所以你实际上需要重新思考你的逻辑，无论如何

既然你似乎没有完全理解这个问题，让我们重新表述一下:

当你的代码读取字符串"ATTATTAATTA";它首先看到第一个"ATTA"然后转到下一个索引，也就是下一个"然后检查字符串的其余部分。字符串的其余部分为"TTAATTA"它只包含一个时间"ATTA"你的代码返回1，但实际上有两个连续的"ATTA"在字符串

中要得到正确的答案，你需要做的是试着从每个字母开始，所以你需要先检查"ATTATTAATTA"然后"TTATTAATTA"然后"TATTAATTA"然后"ATTAATTA"最后得到正确的结果2。

老实说，一个好主意可能是看看这个线程中的其他答案，看看他是如何做到的，我确保他也看了这个问题:)

Answer 2

我为你的代码写了一个更清晰的实现:

#include <iostream>
size_t longestStr(std::string dna, std::string str)
{
size_t temp_ans = 0, final_ans;
for (size_t i = 0; i < dna.size(); i++)
{
if (dna[i] == str[0])
{
final_ans = 0;
while (dna.substr(i, str.size()) == str)
{
if (++final_ans > ans)
{
ans++;
}
i += str.size();
}
i -= (str.size() * final_ans);
}
}
return ans;
}
int main()
{
std::cout << longestStr("GTATTAATTAATTAATTAGTAATTAATTAATTAATTAATTAATTAGTA", "ATTA");
}

输出:

6

不需要temp。
你也应该最好使用size_t而不是int，因为max size of a string > int。