Саптар боюнча алгоритмдер: хэштөө жана KMP
Сапчаларды O(1) убакытта салыштыруу үчүн полиномдук хештер жана үлгүнү издөө үчүн префикс-функция (KMP).
Сапчаларды символ-символ салыштыруу — бир салыштырууга O(n). Эки курал бул чектөөнү алып салат.
Полиномдук хеш: сапка h = s[0]·p^(k-1) + s[1]·p^(k-2) + ... саны модуль боюнча дал келтирилет. Префикстик хештерди жана p даражаларын алдын ала эсептеп алсак, КААЛАГАН сапчанын хеши O(1) убакытта алынат — жана барабар сапчалардын хештери барабар. Ар башка сапчалар теориялык жактан хеши боюнча дал келиши мүмкүн (коллизия), бирок модуль ~10⁹ болгондо ыктымалдык жокко эсе, ал эми параноиктер үчүн кош хеш бар.
Сапчаларды хештер менен салыштыруу. Киргизиңиз: abacaba 2, андан кийин «l1 r1 l2 r2» суроолору: 1 3 5 7 жана 1 2 2 3
Мисалда: abacaba сабынын [1,3] жана [5,7] сапчалары — экөө тең «aba» (YES), ал эми [1,2] менен [2,3] — «ab» жана «ba» (NO).
Экинчи курал — префикс-функция: pi[i] — саптын i позициясында бир учурда анын суффикси да болгон эң узун өздүк префиксинин узундугу. O(n) убакытта эсептелет жана КМП алгоритминин негизинде жатат: тексттен үлгүнү табуу үчүн «үлгү # текст» деп чаптап, pi үлгүнүн узундугуна барабар болгон позицияларды издеңиз.
КМП: үлгүнүн бардык кездешүүлөрү. Киргизиңиз: ababcab ab
Мисалда ab үлгүсү ababcab ичинде 1, 3 жана 6 позицияларында табылат.
Алгоритмдин жүрөгү — while j = pi[j-1] цикли: дал келбегенде башынан баштабайбыз, кийинки талапкер-префикске кайтабыз. Жалпысынан j көрсөткүчү өскөндөн көп кемибейт — ушундан O(n).
Тапшырма: префикс-функциянын жардамы менен саптын эң кичине мезгилин табыңыз (кеңеш: n - pi[n-1], эгер n ушул мааниге бөлүнсө).
Сабакты өттүм деп белгилеңиз.