如何在字符串列表中的所有項目之間找到公共部分？

Question

我有一個保存文件名的QStringList。尋找共同根源的正確方法是什麼？也就是他們共同的左邊部分？

我正在寫C++和使用Qt。

Answer 1

橫移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; 
} 

Answer 2

下面是一個算法：

• 拍攝第一字符串作爲根。
• 對於在列表中的每個項
  • 如果根長於項
    • 根。 truncate（item .length（））;
  • 對於每個索引我在根
    • 如果根 [我]不匹配項 [我]
      • 根。 truncate（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 3

沒有準備解決方案，但編寫新代碼僅需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; 
}