Изменения

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