如何搜索字符串/字符数组中的模式？

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的长度。

请注意，此问题可能存在多种解决方案。当存在解决方案时，该算法找到解决问题的第一个“词典”索引集合。