在字符串中搜索模式

Question

我真的很難獲得遞歸，但我嘗試遞歸匹配字符串內的模式。

假設我有一個字符串怪纔怪才和我有一個模式EKS到match.I可以用許多方法有像正則表達式，找到字符串類的方法，但我真正想做的事情這件事通過遞歸。

要做到這一點我想這個代碼：

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

你永遠不會得到pattern at 2，因爲compare不能這樣工作。問問你自己，

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

return？那麼根據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; 
}