76
правок
Изменения
→Поиск строки максимальной длины, ветвящейся влево и вправо 1.0
'''Строка <tex>s</tex> называется ветвящейся вправо в <tex>t</tex>''' (англ. ''right branching string''), если существуют символы <tex>c</tex> и <tex>d</tex>, такие что <tex>c</tex> <tex>\ne</tex> <tex>d</tex> : <tex>sc</tex> и <tex>sd</tex> {{---}} подстроки <tex>t</tex>. Аналогично, '''ветвящаяся влево''' (англ. ''left branching''), если <tex>cs</tex> и <tex>ds</tex> {{---}} подстроки <tex>t</tex>.
}}
{{Определение
|definition=
'''Левый символ''' для позиции <tex>i</tex> строки <tex>S</tex> {{---}} это символ <tex>S(i-1)</tex>.
}}
Что бы найти максимальную строку, ветвящуюся влево и вправо, строится суффиксный массив из которого исключается суффикс равный самой строке, к примеру для строки <tex>aabcabd</tex> :
{| class="wikitable" border = 1
|-
!Суффиксный массив
|- style = "text-align = right"
| 1 |<tex>abcabd</tex>
|-
| 2 |<tex>abd</tex>
|-
| 3 |<tex>bcabd</tex>
|-
| 4 |<tex>bd</tex>
|-
| 5 |<tex>cabd</tex>
|-
| 6 |<tex>d</tex>
|}
Далее вычисляется <tex>LCP</tex> для суффиксного массива, и находятся левые символы суффиксов:
{| class="wikitable" border = 1
|-
!Левый символ
!Суффиксный массив
!LCP
|- style = "text-align = center"
| 1 |<tex>a</tex>||<tex>abcabd</tex>||<tex>\#</tex>
|-
| 2 |<tex>c</tex>||<tex>abd</tex>||<tex>2</tex>
|-
| 3 |<tex>a</tex>||<tex>bcabd</tex>||<tex>0</tex>
|-
| 4 |<tex>a</tex>||<tex>bd</tex>||<tex>1</tex>
|-
| 5 |<tex>b</tex>||<tex>cabd</tex>||<tex>0</tex>
|-
| 6 |<tex>b</tex>||<tex>d</tex>||<tex>0</tex>
|}
Максимальная строка, ветвящаяся влево и вправо, находится путём проверки значений <tex>LCP</tex> и левого символа:
Ветвление вправо:
*Если <tex>LCP</tex> от пары суффиксов <tex>s_1</tex> и <tex>s_2</tex> больше нуля и не равен длинам этих суффиксов, то строка <tex>s</tex>, равная <tex>s_1[1..LCP(s_1,s_2)]</tex>, ветвится вправо.
Ветвление влево:
*Если левые символы <tex>s_1</tex> и <tex>s_2</tex> не равны, то строка <tex>s</tex>, равная <tex>s_1[1..LCP(s_1,s_2)]</tex>, ветвится влево.
Если выполнены оба условия, то строка ветвится вправо и влево.
С помощью этой проверки находится максимальная строка, ветвящаяся влево и вправо, за <tex>O(n)</tex>.
==См. также==
