8
правок
Изменения
→Доказательство основной леммы
|statement= Пусть <tex>P_{1}=T[p_{1}..j]</tex> — префикс строки <tex>T[\mu..j]</tex> и пусть <tex>P_{2}=T[p_{2}..j]</tex>, где <tex>T[p_{2}..j]</tex> — максимальный суффикс в <tex>Suf [i,p_{1}-1]</tex>. Если <tex>P_{1}</tex> не является префиксом <tex>P_{2}</tex>, тогда <tex>\mu=p_{1}</tex>. Иначе, <tex>P_{2}</tex> также является префиксом строки <tex>T[\mu..j]</tex>.
|proof= Пусть <tex>T[p_{1}..]</tex> — максимальный суффикс в <tex>Suf [i,\ r]</tex> и <tex>T[p_{2}..]</tex> — максимальный суффикс в <tex>Suf [i,\ p_{1}-1]</tex>. Очевидно, <tex>P_{1}=T[p_{1}..j]</tex> является префиксом строки <tex>T[\mu..j]</tex>. Предположим, что <tex>P_{1}</tex> — префикс (иначе <tex>P_{2} \ </tex> (иначе <tex>p_{1}=\mu\</tex> по Лемме 9). Длины <tex>P_{1}</tex> и <tex>P_{2}</tex> различаются не более чем в два раза, поэтому <tex>2|P_{1}|\geq|P_{2}|</tex>. Благодаря этому, <tex>P_{1}</tex> и <tex>P_{2}</tex> имеют некоторые интересные свойства, описанные в последующих леммах. Эти леммы по существу повторяют Леммы 4 и 5 из [http://link.springer.com/chapter/10.1007/978-3-642-38905-4_5#page-1 6], но здесь мы приводим доказательства вследствие другого обозначения.
}}
