c++ - 文字列リスト内のすべての項目から共通部分を見つける方法は?

Question

ファイル名を保持する QStringList があります。それらの共通根、つまり共通左部分を見つける正しい方法は何でしょうか?

私はc ++で書いており、Qtを使用しています。

Answer 1

アルゴリズムは次のとおりです。

• 最初の文字列をrootとして取得します。
• リスト内の各項目について
  • ルートが項目より長い場合
    • ルート。切り捨て( item .length());
  • ルートの各インデックスiについて
    • ルート[ i ] がアイテム[ i ] と一致しない場合
      • ルート。切り捨て( i );

編集:私がテストしていないが、「動作するはず」の一部のコード。

C++03 コード:

QString find_root(const QStringList& list)
{
    QString root = list.front();
    for(QStringList::const_iterator it = list.begin(); it != list.end(); ++it)
    {
        if (root.length() > it->length())
        {
            root.truncate(it->length());
        }

        for(int i = 0; i < root.length(); ++i)
        {
            if (root.at(i) != it->at(i))
            {
                root.truncate(i);
                break;
            }
        }
    }

    return root;
}

C++11 コード:

QString find_root(const QStringList& list)
{
    QString root = list.front();
    for(const auto& item : list)
    {
        if (root.length() > item.length())
        {
            root.truncate(item.length());
        }

        for(int i = 0; i < root.length(); ++i)
        {
            if (root[i] != item[i])
            {
                root.truncate(i);
                break;
            }
        }
    }

    return root;
}

Answer 2

すぐに使える解決策はありませんが、新しいコードを書くのはわずか 5 分です。

int commonBeginningLength(const QString &a, const QString &b) {
    int maxLen = qMin(a.length(), b.length());
    int i=0;
    for(int i=0; i<maxLen; ++i)
        if (a.at(i)!=b.at(i))
            break;
    return i;
}

QString comonBegining(const QStringList &list) {
    if (list.isEmpty())
       return QString();
    QString result(list.front());
    for(int i=1; i<list.count(); ++i) {
        result = result.left(commonBeginningLength(result, list.at(i)));
    }
    return result;
}