这是用 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
最佳答案
您当前的代码在 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 )
关于c++ - 我能做些什么来加速这段代码(字符串相似度)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17865553/