«abacabaabacab» үлгісі үшін Кнут–Моррис–Пратт алгоритмінің префикс-функциясы былай анықталады: π[i] — үлгінің алғашқы i + 1 таңбасынан тұратын бөліктің басымен де, соңымен де сәйкес келетін ең ұзын меншікті (бүкіл бөліктің өзі емес) қиындысының ұзындығы. Индекстер 0-ден басталады. π[12] неге тең?
Дұрыс жауабы мен түсіндірмесі
Жауабы: 6
Ұзындығы 6 префикс «abacab» соңғы 6 таңбамен («abacab») сәйкес. Ұзындығы 7 префикс «abacaba» соңғы 7 таңбаға («aabacab») тең емес, одан ұзынырақтар да сәйкес келмейді. π[12] = 6.
«Алгоритмдер және программалау» тақырыбынан тағы
- «algoritm» жолын «logarifm» жолына түрлендіру үшін қажет Левенштейн қашықтығы (бір таңбаны енгізу, жою немесе...
- run("5 2 *") орындалып, содан кейін print(run("3 +"), st) шақырылады. Нәтиже қандай?
- k.txt файлы UTF-8 кодтауында екі жолдан тұрады: «Қазақ» және «тіл» (әр жол n-мен аяқталады, барлық әріптер — к...
- Разрядтар бойынша сұрыптау (LSD radix sort, тұрақты) [170, 45, 75, 90, 802, 24, 2, 66, 311, 129] массивіне қол...
- Деректер құрылымын оның типтік қолданылуымен сәйкестендіріңіз.
- Бағытталмаған салмақты граф қырлары (қыр: салмақ): A–B: 7, A–D: 5, B–C: 8, B–D: 9, B–E: 7, C–E: 5, D–E: 15, D–...
- Бағытталмаған граф көршілік тізімі арқылы берілген (төбе: көршілері): 1: 2, 3; 2: 1, 4, 5; 3: 1, 5, 6; 4: 2, 7...
- Тапсырмалар арасындағы тәуелділіктер (X→Y — X тапсырмасы Y-тен бұрын орындалуы тиіс): D→A, E→B, A→C, B→C, C→F,...