在为不同的算法计时时需要做一些工作,但是,我在不同站点上多次发现的蛮力实施有时会返回比Notepad ++搜索或VSCode搜索更多的结果。不知道我在做什么错。
该程序将打开一个txt文件,该文件的DNA链长度为10000000,并搜索并计算通过命令行传入的字符串的出现次数。
算法:
int main(int argc, char *argv[]) {
// read in dna strand
ifstream file("dna.txt");
string dna((istreambuf_iterator<char>(file)), istreambuf_iterator<char>());
dna.c_str();
int dnaLength = dna.length();
cout << "DNA Strand Length: " << dnaLength << endl;
string pat = argv[1];
cout << "Pattern: " << pat << endl;
// algorithm
int M = pat.length();
int N = dnaLength;
int localCount = 0;
for (int i = 0; i <= N - M; i++) {
int j;
for (j = 0; j < M; j++) {
if (dna.at(i + j) != pat.at(j)) {
break;
}
}
if (j == M) {
localCount++;
}
}
差异可能是因为你的算法也计算了重叠的结果,而使用Notepad ++进行的快速检查显示却没有。例子:
让dna为“ FooFooFooFoo”
还有你的模式“ FooFoo”
你期望得到什么结果?Notepad ++显示2(一个从位置1开始,第二个从位置7开始(在第一个之后)。
你的算法将找到3(位置1、4和7)
是的,这就是原因。谢谢你。我需要逐步了解并解决该问题。虽然,我可能实际上认为重叠是更好的选择。