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";
}
}
}