Изменения

Даны два конечных списка <tex>A = (a_1, \dots, a_n)</tex> и <tex>B = (b_1 ,\dots ,b_n)</tex>, где <tex>a_i \in \Sigma ^*</tex> и <tex>b_i \in \Sigma ^*</tex> для всех <tex>i</tex>. Вопрос существования непустой последовательности индексов <tex>(i_1 , \dots, i_k)</tex>, удовлетворяющей условию <tex>a_{i_1} \dots a_{i_k} = b_{i_1} \dots b_{i_k}</tex>, где <tex>1 \leqslant i_j \leqslant n</tex> для всех <tex>j</tex>, называется '''проблемой соответствий Поста (ПСП)'''. Такую последовательность индексов, в случае её существования, называют '''решением проблемы соответствий Поста'''.