java - 模式搜索算法

Question

我的字母很少，想找到经常出现的模式。

我有以下字母:

 ---------TAAA-GAGAG----T--T-------T
 -------------T------A---------T----
 ----------AAA-GAGAG---C-----------T
 ------C------------T-A----T-----TA-
 -----AC----------------TT--------C-
 -------------------T---------------
 ---A---------------T---------------
 -------------------------T----T----
 ------C---------------------T-----T
 ----------AAA-GAGAG---C------------
 ----A--------------------T-------A-
 --------G-G-----------G-------T----
 ----A--------------------T---------
 ---------T-------------------------
 -----AC------T--------------------T
 --GA-G------------GT--------------T
 -----A--G-AAA-GAGAG-AA-------------
 -----------------------------------
 -T-------C-G-------T---TT------T--T
 TT-----------------T---------------
 -------------------T---TT-T--------
 ---A----G------------A--------T----
 -----------------------------------
 -------T--AA--G-GAG---C------------
 -T-A----------------A--------------
 ------------T------------------T---
 -----------G-----------------------
 --G-A------------------C---T---T---
 ----A---G---A-------A------T-------
 --------G-------------------T-----T
 -TG--------A---------A-T-----------
 --G--A--------GAGAG---CT-----------
 ---A-------G------------T----G---A-
 T-------G----T---------------------
 -T----C-GCAA--GAGAG-A-C-----T--TT--
 -----A----AAA-GAGAG-A-T------G---A-
 -T---------G-----------------------
 ---A---T---------------------G-----
 ---A---------T-------A---T---A---A-
 -----------------------------------
 TC--A----T----------G-------T-T--G-
 -T----CT---G-T-----T-A----T-T--T---
 -------------T-----TA------------A-
 --G----T-----------------T-T--T----
 ---A------AA--GAGAG---C-----T------
 --------------GAGAG-A-C------------
 ----------AA--GAGAG---C-G----------

如您所见，中间有一个模式:“GAGAG”，所以我可以说 G+A+G+A+G 来自相同的数据。

我想拆分那个行和组。

错误的大小写。第一行有 T+A+A+A 但另一行没有T+A+A+A ，只有 A+A+A 总是在一起。所以在这种情况下 T 和 A 不是组。

任何人都知道这种相关算法或如何找到模式。

我尝试使用 Java 编程。

谢谢。

更新----------------------------------------

1) 模式是否有最小要求长度？- 二。并且不必是连续的位置。

2) “-”符号可以是模式的一部分吗？- 否。"-"表示该位置可以是任何字符，如"undefined"。

3) pattern 是否应该放在每一行中完全相同的索引上？- 是的(但有些行可能是 -)

4) 模式出现的最小次数是多少(出现 2 次就够了吗？)- 这还没有决定，只是想首先找到出现次数最多的位置，然后再找到最好的位置。

Answer 1

您可以创建一个 https://en.wikipedia.org/wiki/Suffix_array和 https://en.wikipedia.org/wiki/LCP_array并在 Least Common Prefix 数组中查找长公共(public)前缀，这意味着子字符串再次出现。