Алгоритмы отыскания совершенных повторов. Метод, основанный на хешировании

Пример функции расстановки с наложениями:
h2(xi) = H(xi) mod M M

Алгоритмы отыскания совершенных повторов Хеширование. Пример.

Пример. S = abcdabcbcbabcd;
l =

Алгоритмы отыскания совершенных повторов Хеширование. Пример. Модульная функция

Пример. S = abcdabcbcbabcd;

Пример списковой схемы устранения наложений

abcdabcbcbabcd
650563533665

l-граммные деревья — это структура данных, представляющая все l-граммы в виде

Префикс−идентификатор pr(i) позиции i в тексте T − кратчайшее подслово, начинающееся

Алгоритм Мартинеца на примере T# = abacbcbacb#
Первый этап построения

11

#

a

b

c

abacbcbacb#

1,3,8

2,5,7,10

4,6,9

Алгоритм Мартинеца на примере T# = abacbcbacb#

b

11

#

c

6

9

4

1

3

2

7

5

10

a

a

a

b

b

b

b

c

c

c

c

c

c

#

#

#

#

abacbcbacb#

8

1,3,8

3,8

2,5,7,10

3,8

2,7

2,7

2,7

4,6,9

4,6,9

Пример компактного префиксного дерева для T# = abacbcbacb#

11

#

c

6

9

4

1

3

8

2

7

5

10

a

acb

a

b

b

cb

c

cb

c

c

#

#

#

#

Пример дерева всеx суффиксов для T# = abacbcbacb#
i suf(i)
abaсbcbacb#
baсbcbacb#
aсbcbacb#
сbcbacb#
bcbacb#
cbacb#

Суффиксное дерево для T# = abacbcbacb#

11

#

cbacb#

6

9

4

1

3

8

2

7

5

10

a

acb

acb#

b

bacbcbacb#

cb

cbacb#

cb

cbacb#

cbacb#

#

#

#

#

Задачи, решаемые с помощью суффиксного дерева:
Вычисление параметров полного частотного спектра;
Поиск образца;
Последовательный