我该如何加速这段代码（字符串相似度）？

Question

这是一个使用标准库编写的C++代码，用于查找字符串S与其后缀的相似度。

尽管它能给出正确的结果，但对于较长的字符串而言，它需要花费很长时间。以下是代码：

#include <iostream>
#include <string>
using namespace std;

int sim(string a, string b){
    int count=0;
    int sa=a.size();
    int sb=b.size();
    int iter;
    if(sa>sb) iter=sb;
    else iter=sa;
    for(int i=0; i<iter; i++){
        if (a[i]!=b[i]) break;
        else count++;
    }
    return count;
}

int strsim(string a){
    int sum=0;
    int s=a.size();
    for(int i=0; i<s; i++){
        sum=sum+sim(a,a.substr(i));
    }
    return sum;
}

int main(){
    int n;
    cin >> n;
    string a[n];
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    for(int i=0; i<n; i++){
        cout << strsim(a[i]) << '\n';
    }
}

约束条件： 每个字符串的长度最多为100000，仅包含小写字符，并且测试用例的数量“n”不能超过10。

样本输入/输出：

输入：

1 ababaa

输出：

11

即，6 + 0 + 3 + 0 + 1 + 1 = 11。

- Ranveer

---

可以将函数中的字符串参数作为常量引用而不是副本传递。并且还可以通过编译器开启更多的优化。 - Some programmer dude

a.substr(i)返回一个全新的字符串，这会产生动态分配。将你的函数改为使用迭代器（这是大多数C++算法的风格），这样你就可以将不同的迭代器传递到字符串中。 - GManNickG

或者你可以切换到使用 char *，在你的 strsim 函数中将 a 与 &a[i] 进行比较。 - user2553780

你的例子是错误的 - 结果应该是12。第二个0应该是1。 - rabensky

Answer 1

您当前的代码计算单个长度为L的字符串，时间复杂度为O(L^3)（substr需要线性运行时间）。更不用说由于字符串传递效率低下而导致的高常数成本。

您的算法可以简化为查找一个字符串与其所有后缀的最长公共前缀。这可以使用后缀数组轻松完成。该概念无法作为答案解释，因此我强烈建议您阅读此文档。

一个次优且易于编码的后缀数组解决方案将具有O(Llg^2(L))（L =字符串长度）的构建时间和使用范围最小查询查询2个后缀的最长公共前缀的O(1)时间。请注意，整个字符串本身就是它自己的后缀。在您的情况下，您需要对每个字符串进行L个查询。因此，一个字符串的总复杂度将为O(Llg^2(L)) + O(L)。

如果您想进一步改进，可以通过使用基数排序将构建时间降低到O(Llg(L))，或者将其降低到O(L)（阅读）。

- nims

Answer 2

您在这里的最大成本是，您通过值传递字符串 - 这意味着每次调用“sim”都会创建两个全新的字符串并将数据复制到它们中。您应该消除这种情况，并将其替换为按引用传递。

#include <iostream>
#include <string>
#include <vector>
using namespace std;

size_t compareSubstring(const std::string& str, size_t offset)
{
    size_t count = 0;
    std::string::const_iterator lhsIt = str.begin();
    std::string::const_iterator rhsIt = str.begin() + offset;
    for ( ; rhsIt != str.end() ; ++lhsIt, ++rhsIt ) {
        if (*lhsIt != *rhsIt)
            break;
        ++count;
    }
    return count;
}

int compareString(const string& str)
{
    size_t count = 0;
    const size_t length = str.size();
    for(size_t i = 0; i < length; ++i) {
        count += compareSubstring(str, i);
    }
    return count;
}

int main()
{
    size_t numStrings = 0;
    std::cin >> numStrings;

    std::vector<std::string> strings;
    strings.resize(numStrings);

    for(size_t i = 0; i < numStrings; ++i) {
        std::cin >> strings[i];
    }

    for(size_t i = 0; i < numStrings; ++i) {
        std::cout << compareString(strings[i]) << std::endl;
    }
}

- kfsone

---

这段代码将OP的代码从“O（L ^ 3）”降低到“O（L ^ 2）”，同时减小了常数因素。但是，由于L可以增加到100000，所以“O（L ^ 2）”仍然是不切实际的。 - nims

Answer 3

这是最有效的方法（不涉及FFT领域）：

sum_i=0^j sum_j=0^s f_i,j

int strsim(const string &a){
    int s=a.size();
    int sum=0;
    for(int i=0; i<s; i++){
        for (int j=i;j<s;++j){
            if (a[j-i]!=a[i]) break;
            sum ++;
        }
    }
    return sum;
}

我知道它看起来与你的代码不同，但（除非我有错误）它应该返回相同的结果。

试一下并让我知道！

- rabensky

Answer 4

首先您应该检查是否存在更好的算法。然后，根据您愿意投资和牺牲可移植性的程度，如果编译器未能实现，您可能希望手动矢量化代码。使用gcc固有函数（参见例如本教程），我已经成功将类似代码的速度提高了6倍。

- hivert

Answer 5

在您的strsim()函数中增加一行代码可以减少对sim()函数的额外调用。我们知道，当我们谈论性能时，函数调用的成本(消耗额外的内存和处理"前奏"和"尾声"机制)是相当可观的。

因此，只有在两个字符串的第一个字符相等的情况下，才调用sim函数，即在您的情况下为"a"和"a.substring"。

     int strsim(string a){
     int sum=0;
     int s=a.size();
     for(int i=0; i<s; i++){

     if(a[i] == a[0])  //add this extra line
     sum=sum+sim(a,a.substr(i));

     }
    return sum;
   }

- Raju

---

a.substr(i)[0] 是一个糟糕的建议。请使用 a[i]。 - rabensky

@cluracan，你是对的，我想过了这个问题，但没有时间去编辑它，不管怎样还是谢谢。:) - Raju