文字列内のパターンを検索する

Question

私は本当に再帰を得るのに苦労していますが、文字列の中のパターンにマッチする再帰を試みました。

と仮定私は、文字列にオタクためオタクを持っていると私は、文字列クラスの方法を見つける match.IにEKSが正規表現、のようにそこに多くの方法を使用することができ、パターンを持っていますが、私は本当にやりたいです再帰によるこのこと。

void recursion(int i,string str) 
{ 
    if(!str.compare("eks")) 
     cout<<"pattern at :"<<i<<'\n'; 

    if(i<str.length() && str.length()-1!=0) 
     recursion(i,str.substr(i,str.length()-1)); 
} 

int main() 
{ 
    string str("geeks for geeks"); 

    for(int i=0;i<str.length();i++) 
     recursion(i,str.substr(i,str.length())); 
} 

出力：

理想の出力リレー：

pattern at 2 
pattern at 12 

何私がここで間違っていることができ、何だろう、私はこのコードを試してみました、これを達成するために

再帰でこれを行うには良い方法でしょうか？

私はcppの多くのトピックを理解しましたが、再帰を使って、どのように動作するのかを知っています。再帰で何かをコーディングしようとすると、決してうまく動作しません。まあ？

Answer 1

compareはそのようには機能しないので、pattern at 2は決して得られません。

std::string("eks for geeks").compare("eks") 

リターン？さて、documentationによれば、"eks for geeks"が"eks"より長いため、何か肯定的なものが得られます。最初の手順はこれを修正することです：

void recursion(int i, std::string str){ 
    if(!str.substr(0,3).compare("eks")) { 
    std::cout << "pattern at: " << i << '\n'; 
    } 

次に、私たちは再帰する必要があります。しかし、何かがあります。 iは "カーソル"の現在の位置でなければなりません。したがって、あなたはそれを進める必要があります。

i = i + 1; 

そして、我々はすべての反復で、文字列の長さを短くすれば、我々はi < str.lengthをテストしてはならない、そうでなければ我々は、文字列の後半をチェックしません。

if(str.length() - 1 > 0) { 
    recursion(i, str.substr(1)); 
    } 
} 

を

私たちは実際にこのコードをコンパイルする前に、それについての理由は聞かせて：

• 我々は"eks"
との比較のために正しい長さの部分文字列を持っています
• 私たちは、私たち「事前」我々はいくつかの点
で空の文字列で終わるだろう最初の文字
• を除去することにより、文字列を
• を再帰的にする前に、我々は位置を進め、現在位置
• 以外iを使用することはありません

は、合理的なようだ：

#include <iostream> 
#include <string> 

void recursion(int i, std::string str){ 
    if(!str.substr(0,3).compare("eks")) { 
    std::cout << "pattern at: " << i << '\n'; 
    } 

    i = i + 1; 

    if(str.length() - 1 > 0) { 
    recursion(i, str.substr(1)); 
    } 
} 

int main() { 
    recursion(0, "geeks for geeks"); 
    return 0; 
} 

出力：

pattern at: 2 
pattern at: 12 

しかし、これは最適ではありません。いくつかの最適化が可能です。しかし、それは運動として残されています。

演習

1. compareは、それはアルゴリズムだのためにsubstrを使用する必要があります。 substrが不要な独自の比較関数を記述してください。
2. 多くのコピーが行われています。あなたはそれを取り除くことができますか？
3. forループが間違っていました。どうして？

Answer 2

再帰関数はループ内で実行してはなりません。そして、いくつかの間違いがあります。このコードを試してみてください。

void recursion(string str, string subStr, int i){ 
    if(str.find(subStr) != string::npos) { 
     int pos = str.find(subStr); 
     str = str.substr(pos + subStr.length(), str.length()-1); 
     cout << "pattern at " << (pos + i) << endl; 
     recursion(str, subStr, pos+subStr.length()); 
    } 
} 

int main(int argc, char** argv) { 
    string str("geeks for geeks"); 
    string subStr("eks"); 
    recursion(str, subStr, 0); 
    return 0; 
}