如何搜索字符串/字符數組中的模式？

Question

我需要在由用戶給出的輸入中查找模式。如果找到了，則返回（開始，結束）位置。

例如： -

輸入= A B C D B C A D

模式尋找= D C A

輸出= 3,6

圖案不必連續發生。

它可以像D是在輸入的開始，C在中間和A在結束。 - 一個有效的場景。

我對此感到困惑的兩件事。

• 如何接受輸入？作爲一個數組？如果是，那麼作爲一個字符串或字符數組？

• 如何查找圖案？

Answer 1

輸入格式在這裏並不重要：您可以將字符串和序列都作爲字符串。訣竅在於決定使用哪種算法來解決問題。

在這種情況下，一個貪婪的策略將工作：

• 閱讀兩個字符串，S（串）和P（模式）。
• 設置兩個索引 - si爲字符串，pi爲模式，並將它們都設置爲零。
• 搜索字母P.charAt(pi)在S從si開始。如果字母不能從si到端子串中找到，則該圖案中不存在
• 否則，採取的P.charAt(pi)第一次出現在S，由一個設置si該索引加一，和預先pi。
• 如果您到達P的末尾，則完成
• 否則，返回到搜索步驟，並繼續處理，直到找到模式或耗盡字符串。
• 如果您需要打印序列的索引，請添加一個索引數組，並在您隨時填寫索引。數組的長度應該等於P的長度。

請注意，此問題可能存在多種解決方案。當存在解決方案時，該算法找到解決問題的第一個「詞典」索引集合。