任何人都可以帮助我优化我的 LONGEST COMMON SUBSTRING 问题吗？我必须读取非常大的文件（最大 2 Gb），但我不知道要使用哪种结构...在 c++ 中没有哈希映射。TBB 中有并发哈希映射，但使用起来非常复杂算法。我用 **L 矩阵解决了这个问题，但它很贪心，不能用于大输入。矩阵充满了零，这可以通过使用 map> 来消除，并且只存储非零，但这真的很慢并且实际上不可用。速度非常重要。这是代码：
// L[i][j] will contain length of the longest substring
// ending by positions i in refSeq and j in otherSeq
size_t **L = new size_t*[refSeq.length()];
for(size_t i=0; i<refSeq.length();++i)
L[i] = new size_t[otherSeq.length()];
// iteration over the characters of the reference sequence
for(size_t i=0; i<refSeq.length();i++){
// iteration over the characters of the sequence to compare
for(size_t j=0; j<otherSeq.length();j++){
// if the characters are the same,
// increase the consecutive matching score from the previous cell
if(refSeq[i]==otherSeq[j]){
if(i==0 || j==0)
L[i][j]=1;
else
L[i][j] = L[i-1][j-1] + 1;
}
// or reset the matching score to 0
else
L[i][j]=0;
}
}
// output the matches for this sequence
// length must be at least minMatchLength
// and the longest possible.
for(size_t i=0; i<refSeq.length();i++){
for(size_t j=0; j<otherSeq.length();j++){
if(L[i][j]>=minMatchLength) {
//this sequence is part of a longer one
if(i+1<refSeq.length() && j+1<otherSeq.length() && L[i][j]<=L[i+1][j+1])
continue;
//this sequence is part of a longer one
if(i<refSeq.length() && j+1<otherSeq.length() && L[i][j]<=L[i][j+1])
continue;
//this sequence is part of a longer one
if(i+1<refSeq.length() && j<otherSeq.length() && L[i][j]<=L[i+1][j])
continue;
cout << i-L[i][j]+2 << " " << i+1 << " " << j-L[i][j]+2 << " " << j+1 << "\n";
// output the matching sequences for debugging :
//cout << refSeq.substr(i-L[i][j]+1,L[i][j]) << "\n";
//cout << otherSeq.substr(j-L[i][j]+1,L[i][j]) << "\n";
}
}
}