C++ の一連のファイル名から最長の共通部分文字列を計算する必要があります。
正確には、std::strings の std::list があります (または QT に相当するものも問題ありません)。
char const *x[] = {"FirstFileWord.xls", "SecondFileBlue.xls", "ThirdFileWhite.xls", "ForthFileGreen.xls"};
std::list<std::string> files(x, x + sizeof(x) / sizeof(*x));
すべての文字列の n 個の異なる最長共通部分文字列を計算する必要があります。この場合、たとえば n=2 の場合です。
"File" and ".xls"
最長の共通部分列を計算できれば、それを切り取り、アルゴリズムを再度実行して 2 番目に長い部分列を取得できます。つまり、基本的には次のようになります。
std::strings の std::list の LCS を計算するための (リファレンス?) 実装はありますか?
これは良い答えではありませんが、私が持っている汚い解決策です-最後の「/」の後の部分のみが取得されるQUrlのQListに対するブルートフォース。これを「適切な」コードに置き換えたいと思います。
(私はhttp://www.icir.org/christian/libstree/を発見しました - これは非常に役立ちますが、私のマシンでコンパイルすることはできません。誰かがこれを使用したのでしょうか?)
QString SubstringMatching::getMatchPattern(QList<QUrl> urls)
{
QString a;
int foundPosition = -1;
int foundLength = -1;
for (int i=urls.first().toString().lastIndexOf("/")+1; i<urls.first().toString().length(); i++)
{
bool hit=true;
int xj;
for (int j=0; j<urls.first().toString().length()-i+1; j++ ) // try to match from position i up to the end of the string :: test character at pos. (i+j)
{
if (!hit) break;
QString firstString = urls.first().toString().right( urls.first().toString().length()-i ).left( j ); // this needs to match all k strings
//qDebug() << "SEARCH " << firstString;
for (int k=1; k<urls.length(); k++) // test all other strings, k = test string number
{
if (!hit) break;
//qDebug() << " IN " << urls.at(k).toString().right(urls.at(k).toString().length() - urls.at(k).toString().lastIndexOf("/")+1);
//qDebug() << " RES " << urls.at(k).toString().indexOf(firstString, urls.at(k).toString().lastIndexOf("/")+1);
if (urls.at(k).toString().indexOf(firstString, urls.at(k).toString().lastIndexOf("/")+1)<0) {
xj = j;
//qDebug() << "HIT LENGTH " << xj-1 << " : " << firstString;
hit = false;
}
}
}
if (hit) xj = urls.first().toString().length()-i+1; // hit up to the end of the string
if ((xj-2)>foundLength) // have longer match than existing, j=1 is match length
{
foundPosition = i; // at the current position
foundLength = xj-1;
//qDebug() << "Found at " << i << " length " << foundLength;
}
}
a = urls.first().toString().right( urls.first().toString().length()-foundPosition ).left( foundLength );
//qDebug() << a;
return a;
}