コレクション内のすべての文字列に含まれる文字列の部分を切り取る方法

Question

私の現在の問題は次のとおりです。 ファイルへのフルパス名のstd::vectorがあります。 今、私はすべての文字列の共通接頭辞を切り捨てたいと思います。

例

私は、ベクター中にこれらの3つの文字列を使用している場合：

/home/user/foo.txt 
/home/user/bar.txt 
/home/baz.txt 

私は、ベクター内のすべての文字列から/home/を遮断したいと思います。

質問

これを達成する方法はありますか？ すべての文字列の共通接頭辞を削除するアルゴリズムが必要です。 私は現在、唯一のN文字列でO（Nメートル）でこの問題を解決し、メートルだけのcharで他のすべての文字列の文字ですべての文字列を経ることで、最も長い文字列の長さであるという考えを持っています。 これを解決するには、より高速で洗練された方法がありますか？

Answer 1

これは完全にstd :: algorithmsで行うことができます。

概要：

1. すでにソートされていない場合、入力範囲を並べ替えます。ソートされた範囲 の最初と最後のパスは最も類似しません。最良の場合はO（N）、最悪の場合はO（N + N。logN個） 二つの最も異なる経路間larges共通の配列を決定する

2. 使用std::mismatch COUNTが最長共通の文字数である第一COUNT文字を消去する各パススルー[無意味]

3. ランシーケンス。 O（N）

ベストケースの時間計算量：O（2N）、最悪の場合O（2N + N.logN）（？誰かがそれを確認することができます）

#include <iostream> 
#include <algorithm> 
#include <string> 
#include <vector> 

std::string common_substring(const std::string& l, const std::string& r) 
{ 
    return std::string(l.begin(), 
         std::mismatch(l.begin(), l.end(), 
            r.begin(), r.end()).first); 
} 

std::string mutating_common_substring(std::vector<std::string>& range) 
{ 
    if (range.empty()) 
     return std::string(); 
    else 
    { 
     if (not std::is_sorted(range.begin(), range.end())) 
      std::sort(range.begin(), range.end()); 
     return common_substring(range.front(), range.back()); 
    } 
} 

std::vector<std::string> chop(std::vector<std::string> samples) 
{ 
    auto str = mutating_common_substring(samples); 
    for (auto& s : samples) 
    { 
     s.erase(s.begin(), std::next(s.begin(), str.size())); 
    } 
    return samples; 
} 

int main() 
{ 
    std::vector<std::string> samples = { 
     "/home/user/foo.txt", 
     "/home/user/bar.txt", 
     "/home/baz.txt" 
    }; 

    samples = chop(std::move(samples)); 

    for (auto& s : samples) 
    { 
     std::cout << s << std::endl; 
    } 
} 

が期待：

baz.txt 
user/bar.txt 
user/foo.txt 

ここには、並べ替えを必要としない別の `common_substring 'があります。時間の複雑さは、理論のO（N）であるが、それは実際に速いのかどうか、あなたがチェックする必要があるだろう：

std::string common_substring(const std::vector<std::string>& range) 
{ 
    if (range.empty()) 
    { 
     return {}; 
    } 

    return std::accumulate(std::next(range.begin(), 1), range.end(), range.front(), 
          [](auto const& best, const auto& sample) 
          { 
           return common_substring(best, sample); 
          }); 
} 

更新：

エレガンスはさておき、これはおそらく、それがいずれかを回避するので最速の方法ですすべての変換をインプレースで実行します。ほとんどのアーキテクチャとサンプルサイズでは、これは他のパフォーマンス上の考慮事項よりも重要です。

#include <iostream> 
#include <vector> 
#include <string> 

void reduce_to_common(std::string& best, const std::string& sample) 
{ 
    best.erase(std::mismatch(best.begin(), best.end(), 
          sample.begin(), sample.end()).first, 
       best.end()); 

} 

void remove_common_prefix(std::vector<std::string>& range) 
{ 
    if (range.size()) 
    { 
     auto iter = range.begin(); 
     auto best = *iter; 
     for (; ++iter != range.end() ;) 
     { 
      reduce_to_common(best, *iter); 
     } 

     auto prefix_length = best.size(); 

     for (auto& s : range) 
     { 
      s.erase(s.begin(), std::next(s.begin(), prefix_length)); 
     } 
    } 
} 


int main() 
{ 
    std::vector<std::string> samples = { 
     "/home/user/foo.txt", 
     "/home/user/bar.txt", 
     "/home/baz.txt" 
    }; 

    remove_common_prefix(samples); 

    for (auto& s : samples) 
    { 
     std::cout << s << std::endl; 
    } 
} 

Answer 2

すべての文字列を繰り返し処理するだけです。あなただけのプレフィックスのみを短縮することができ、不事実を利用することにより、文字列の全長にわたって反復処理を回避することができます：あなたはもっと前を持っている場合Martin Bonner's answerのヒントから描画

#include <iostream> 
#include <string> 
#include <vector> 

std::string common_prefix(const std::vector<std::string> &ss) { 
    if (ss.empty()) 
     // no prefix 
     return ""; 

    std::string prefix = ss[0]; 

    for (size_t i = 1; i < ss.size(); i++) { 
     size_t c = 0; // index after which the string differ 
     for (; c < prefix.length(); c++) { 
      if (prefix[c] != ss[i][c]) { 
       // strings differ from character c on 
       break; 
      } 
     } 

     if (c == 0) 
      // no common prefix 
      return ""; 

     // the prefix is only up to character c-1, so resize prefix 
     prefix.resize(c); 
    } 

    return prefix; 
} 

void strip_common_prefix(std::vector<std::string> &ss) { 
    std::string prefix = common_prefix(ss); 
    if (prefix.empty()) 
     // no common prefix, nothing to do 
     return; 

    // drop the common part, which are always the first prefix.length() characters 
    for (std::string &s: ss) { 
     s = s.substr(prefix.length()); 
    } 
} 

int main() 
{ 
    std::vector<std::string> ss { "/home/user/foo.txt", "/home/user/bar.txt", "/home/baz.txt"}; 
    strip_common_prefix(ss); 
    for (std::string &s: ss) 
     std::cout << s << "\n"; 
} 

、あなたがより効率的なアルゴリズムを実装することができますあなたの入力に関する知識。 特に、入力がソートされていることがわかっている場合は、最初と最後の文字列を比較するだけで十分です（Richard's answer参照）。

Answer 3

for(vector<string>::iterator itr=V.begin(); itr!=V.end(); ++itr) 
    itr->erase(0,6); 

Answer 4

リスト内のすべての文字列を検索する必要があります。ただし、すべての文字列のすべての文字を比較する必要はありません。共通接頭辞は短くなるだけで、「これまでの共通接頭辞」と比較すればよい。私はこれがビッグオーバの複雑さを変えるとは思っていませんが、実際のスピードとはかなり異なるでしょう。

また、これらはファイル名のようです。それらはソートされていますか（多くのファイルシステムがソートされた順序で物事を返す傾向があることに注意してください）？そうであれば、最初と最後の要素だけを考慮する必要があります。 pr がほとんどの場合は、最初と最後の共通プレフィックスを考慮し、必要に応じて接頭辞をさらに短縮するすべての他の文字列を繰り返します。

Answer 5

i - フォルダの深さが最小（baz.txt）のファイルを探します。ルートパスはhomeです ii - 次に、他の文字列を調べて、そのルートで始まるかどうかを確認します。 iii - そうなら、すべての文字列からrootを削除します。

Answer 6

std::size_t index=0;で始まる。リストをスキャンして、そのインデックスの文字が一致するかどうかを確認します（注：末尾が一致しない場合）。そうであれば、インデックスを進めて繰り返します。

完了すると、インデックスはプレフィックスの長さの値を持ちます。

この時点では、string_viewという文字を書いたり、検索したりすることをおすすめします。そうであれば、開始/終了がindex, str.size()のstrの各文字列に対してstring_viewを作成するだけです。

全体的なコスト：O(|prefix|*N+N)これは、回答が正しいことを確認するための費用です。

string_viewを書きたくない場合は、ベクターのstrにstr.erase(str.begin(), str.begin()+index)と電話するだけです。

全体的なコストはO(|total string length|+N)です。それを確認するためにプレフィックスを訪問しなければならない場合、文字列の末尾を書き換えなければなりません。

今では、あなたはどこにでもメモリを触れているので、幅優先のコストは地域性です。おそらく実際にはチャンクでそれを行う方が効率的でしょう。ここでは、長さQまでの最初のK文字列をスキャンして共通接頭辞を見つけ、その共通接頭辞と次のブロックを連鎖させます。これは、O記法を変更することはありませんが、メモリ参照の局所性を改善します。