java - 如何在字符串/字符数组中搜索模式？

Question

我需要在用户给出的输入中寻找模式。如果找到，则返回（开始，结束）位置。

例如：-

输入 =A B C D B C A D

要寻找的模式 =D C A

输出 =3,6

该模式不必连续出现。

就像 D 在输入的开头，C 在中间，A 在结尾。- 一个有效的场景。

我很困惑的两件事。

• 如何接受输入？作为一个数组？如果是，那么作为 String 或 Char 数组？

• 我如何寻找模式？

Answer 1

输入的格式在这里无关紧要：您可以将字符串和序列都作为字符串。诀窍是决定使用一种算法来解决问题。

在这种情况下，贪婪策略将起作用：

• 读取两个字符串，S(string) 和P(pattern)。
• si为字符串和模式创建两个索引pi，并将它们都设置为零。
• 搜索P.charAt(pi)从S开始的字母si。如果在从到结尾的子字符串中找不到该字母si，则该模式不存在
• 否则，取 in 的第一次出现P.charAt(pi)，S设置si为该索引加一，然后前进pi一。
• 如果你到达终点P，你就完成了
• 否则，返回搜索步骤，继续处理，直到找到模式或耗尽字符串。
• 如果您需要打印序列的索引，请添加一个索引数组，然后随时填写。数组的长度应该等于 的长度P。

请注意，此问题可能有多种解决方案。当存在解决方案时，该算法会找到解决问题的第一组“字典式”索引。