Warm tip: This article is reproduced from serverfault.com, please click

c++-为什么我的蛮力子字符串搜索返回额外的计数?

(c++ - Why is my brute force substring search returning extra counts?)

发布于 2020-11-29 16:11:22

在为不同的算法计时时需要做一些工作,但是,我在不同站点上多次发现的蛮力实施有时会返回比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++;
        }
    }
Questioner
cyberguy
Viewed
0
P. Saladin 2020-11-30 00:50:58

差异可能是因为你的算法也计算了重叠的结果,而使用Notepad ++进行的快速检查显示却没有。例子:

让dna为“ FooFooFooFoo”

还有你的模式“ FooFoo”

你期望得到什么结果?Notepad ++显示2(一个从位置1开始,第二个从位置7开始(在第一个之后)。

你的算法将找到3(位置1、4和7)