* '''Слияние суффиксных массивов'''
Если бы мы умели сливать <tex> A_{S_o} </tex> и <tex> A_{S_e} </tex> за линейное время, получили бы:
{| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| №!style="background-color:#EEE"| Подстрока|-|style="background-color:#FFF;padding:2px 30px"| <tex> 9 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$'''</tex> |-|style="background-color:#FFF;padding:2px 30px"| <tex> 8 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> \$\$'''</tex>|- |style="background-color:#FFF;padding:2px 30px"| <tex> 7 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> a\$\$'''</tex> |-|style="background-color:#FFF;padding:2px 30px"| <tex> 6 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> aa\$\$'''</tex>|- |style="background-color:#FFF;padding:2px 30px"| <tex> 0 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> ababbbaa\$\$'''</tex>|- |style="background-color:#FFF;padding:2px 30px"| <tex> 2 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> abbbaa\$\$'''</tex> |-|style="background-color:#FFF;padding:2px 30px"| <tex> 5 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> baa\$\$'''</tex> |-|style="background-color:#FFF;padding:2px 30px"| <tex> 1 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> babbbaa\$\$'''</tex> |-|style="background-color:#FFF;padding:2px 30px"| <tex> 4 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bbaa\$\$'''</tex>|- |style="background-color:#FFF;padding:2px 30px"| <tex> 3 '''</tex>|style="background-color:#FFF;padding:2px 30px"| <tex> bbbaa\$\$'''</tex>|}
Как и было сказано вначале, избавиться от лишних '''$''' легко, так как суффиксы, им соответствующие, будут первыми в суффиксном массиве (в данном случае достаточно выбросить "9" из суффиксного массива).
