単語が接頭辞であるかどうかを調べるための C++ の関数

StackOverflow https://stackoverflow.com/questions/2482716

  •  21-09-2019
  •  | 
  •  

質問

AB、AAB、AA という単語があるとします。

AB は AAB の接頭辞ではありませんが、AA は AAB の接頭辞です。AA の最後に B を追加するだけで AAB になりますが、AB ではこれは不可能です。

それで、C++（STL）には、2つの単語が他の単語の接頭辞であるかどうかを判断できる機能はありますか？

ありがとう。

役に立ちましたか？

解決 

template<class C, class T, class A>
bool starts_with(std::basic_string<C,T,A> const& haystack,
                 std::basic_string<C,T,A> const& needle)
{
  return needle.length() <= haystack.length() &&
    std::equal(needle.begin(), needle.end(), haystack.begin());
}
長さチェックは時期尚早な最適化ではないことを

注、それが会うのstd ::の同じ前提条件に必要とされます。

他のヒント

std::string full = "AAB", pre= "AA";
bool prefixed = full.find( pre ) == 0;

または何について：

bool prefixed =  full.compare( 0, pre.size(), pre ) == 0;

std::string full = "AAB", lookfor = "AA";
const bool isprefixmatch = (full.substr(0,lookfor.lenght())==lookfor);

この答えはCやC ++で動作し、STLを必要としません。

// test if string2 a prefix of string1
// inputs must be non NULL
// returns TRUE if string2 is a prefix, otherwise FALSE

int isAPrefix(const char *string1,
              const char *string2)
{
    return (strncmp(string1, string2, strlen(string2)) == 0);
}

すでに Boost に依存している場合は、 boost::algorithm::starts_with.

int main()
{
    std::cout << boost::algorithm::starts_with("abba", "ab"); // true
    std::cout << boost::algorithm::starts_with("abba", "ba"); // false
    return 0;
}

見つけるたびに std::string 必要な文字列操作メソッドがありません。チェックしてください。 ブースト文字列アルゴリズム 図書館。

文字列のfindメソッドを使用します。それが返すインデックスは、文字列の先頭にあるかどうかをチェックします。

http://www.cplusplus.com/reference/string/string/このようなもののために目を通すのに良い場所です。それらのほとんどは非常に便利ですので、これらの機能に慣れるために10分かかります。

あなたは他の文字列内のテキストの任意の場所を見つけるために見つける使用することができますが、find_first_ofは、より適切であろう（と接尾辞と比較します）。それ以外の場合はサフィックスを見つけるために、find_last_ofが適切でしょう。

あなたの問題への本当の答えは、私が思うに、プレフィックスツリーを使用しています。受け入れられた答えアルゴリズムは、仕事をするだろうが、あなたは時間内に直線的である他のすべてのあなたの言葉でセットにあなたのプレフィックスwouldbeワードをチェックする必要があります。あなたの手ですべての単語（あなたが他の単語に接頭辞であるすべての単語を取得したいと言う）と、あなたはO（N ^ 2）を持つ複雑さのためにそれを行います。 単語が別の接頭辞であるかどうかを簡単なチェックは、単語の長さに線形である。

プレフィックスツリーを使用すると、対数時間と第二のあなたの最初の質問にお答えします - リニアに。木の高さによって制限 - あなたは、ツリー内の単語を検索し、最後のノードは、（それが存在する拡張長い単語を意味する）の葉でなくなるまで言葉が接頭辞であるかどうかの確認するには、rootアップからダウンだけの散歩です。一方で、ツリーを横断し、最後のノードがすべての接頭語のリストをもたらすであろう葉されていないため、各段階で、現在の単語を書き留めます。あなたは一度だけ、各ノードを訪問するようツリートラバーサルが線形時間で実行されます。

あなただけの1つの文字列を見つけるまたは部分は、uは、単にこのFN

を使用することができます以外の接頭辞である場合 
 std::size_t found = str1.find(str2); //returns position of str2 in str1 (if found==0) than it is prefix else not.

それはそれはゴミ値を返すよりも、存在しない場合 そしてもしUは無いために同じことをやって。文字列とあなたがトライを使用する必要が高速な方法で行うにしたいの。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top