和征服算法 - 在字符串中搜索模式

Question

我試圖用僞代碼編寫一個分而治之的算法，它可以查找在給定的n個字母串中出現了多少個3字母模式。

事情是這樣的僞代碼：

的模式是固定的：XXY

int searchString("CDSXXYZSE") 
    . 
    . 
    search for "XXY" 
    . 
    . 
return (1) 

或者

int searchString("CDSXZXYZSE") 
    . 
    . 
    search for "XXY" 
    . 
    . 
return (0) 

謝謝大家的時間！

Answer 1

在除法步驟中，我會將您的字符串參數拆分爲所有可能的3字母組合，例如（CDS，DSX，XXY ...）。然後，對搜索到的模式進行相等測試，並在征服步驟中加上匹配數量。