c++ - 我能做些什么来加速这段代码(字符串相似度)？

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。

示例 I/O:

输入:

1 ababaa

输出:

11

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

Answer 1

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

您的算法可以简单地简化为查找字符串及其所有后缀的最长公共(public)前缀。这可以使用 Suffix Aray 轻松完成.这个概念不能解释为答案，所以我强烈推荐你read this .

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

如果你想进一步改进，你可以通过使用基数排序将构建时间减少到O(Llg(L))，或者减少到O(L)( Read )