6

这是用 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

IE，6 + 0 + 3 + 0 + 1 + 1 = 11

4

5 回答 5

7

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

您的算法可以简单地简化为查找具有所有后缀的字符串的最长公共前缀。这可以使用Suffix Aray轻松完成。这个概念不能作为答案来解释，所以我强烈建议你阅读这篇文章。

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

如果您想进一步改进，您可以O(Llg(L))通过使用基数排序来减少构建时间，或者O(L)（阅读）

于 2013-07-25T18:22:37.513 回答
3

您在这里的最大成本是您通过值传递字符串 - 这意味着每次调用“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;
    }
}
于 2013-07-25T18:34:15.830 回答
0

首先，您应该检查是否没有更好的算法。然后，根据您准备投入多少和松散的可移植性，如果您的编译器无法做到这一点，您可能希望手动对代码进行矢量化。使用 gcc 内在函数（参见例如本教程）我已经能够在类似的代码上获得 x6 加速。

于 2013-07-25T19:42:17.790 回答
0

这里尽可能高效（无需进入 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;
}

我知道它似乎与您的代码不同，但是（除非我有错误）它应该返回相同的东西。

试试看，让我知道！

于 2013-07-25T19:23:09.450 回答
-1

向您的 strsim() 函数添加一行可以减少对您的 sim() 函数的一些额外的函数调用。正如我们所知，当我们谈论性能时，函数调用的成本（消耗额外的内存和处理“序言”和“尾声”机制）是相当可观的。

因此，仅当您的情况“a”和“a.substring”中两个字符串的第一个字符相等时才调用 sim 函数。

     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;
   }
于 2013-07-25T19:01:04.603 回答