Массив \(a\) массивінің \(b\) массивінің ішкі тізбегі екенін қалай тексеруге болады? Алдымен, \(a_1\) элементінің \(b\) массивінде ең бірінші кездесуін табамыз, содан кейін \(a_2\) элементінің \(a_1\) кейін тұратын кездесуін іздейміз және солай жалғастырамыз, әрқашан ең сол жақтағы қолжетімді кездесуді таңдап. Бұл алгоритмді бұзғымыз келеді.

Мәселені жадтық тәсілмен шешеміз: әр уақытта \(i\) позициясына үміткерді таңдап, оның кездесуі \(i-1\) қадамда табылғаннан кейін тұруы керек, және ол мүмкіндігінше оң жақта болуы керек.

Как проверять что массив \(a\) является подпоследовательностью массива \(b\)? Будем искать самое первое вхождение \(a_1\) в \(b\), затем вхождение \(a_2\) которое стоит позже и так далее, жадно выбирая самое левое доступное вхождение. Мы хотим сломать этот алгоритм.

Будем решать задачу жадно: каждый раз, будем выбирать того кандидата на позицию \(i\), чье вхождение лежит как можно правее, причем вхождение должно быть правее чем то что мы нашли на шаге \(i-1\).