c++ - 如何在字符串列表中的所有项目中找到共同的部分？

Question

我有一个包含文件名的 QStringList。找到它们的共同根，即它们共同的左侧部分的正确方法是什么？

我正在写 c++ 并使用 Qt。

Answer 1

这是一个算法：

• 将第一个字符串作为root。
• 对于列表中的每个项目
  • 如果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;
}

Answer 3

遍历 QStringList，比较根和每个字符串：

QString root(QString &a, QString &b)
{
    QString str;

    for(int i = 0; i < a.length() && i < b.length(); ++i) {
        if(a.at(i) == b.at(i))str.push_back(a.at(i));
        else break;
    }
    return str;
}

QString dosth(QStringList &list)
{
    QString str;
    if(list.isEmpty()) return str;
    for(int i = 0; i < list.length(); ++i) {
        str = root(str, list.at(i));
    }
    return str;
}