266. Кластеризация символьных последовательностей

Есть конечный алфавит $A = \{a_1, a_2, \dots, a_{K-1}, a_K=S\}, a_i \in \{a, b, \dots z\}, S$ — конец строки.

Рассмотрим следующий способ генерации случайных строк над алфавитом $A$.

1. Первый символ $x_1$ — случайная величина с распределением $P(x_1=a_i)=q_i$ (известно, что $q_K=0$).
2. Каждый следующий символ генерируется на основе предыдущего в соответствии с условным распределением $P(x_i=a_j | x_{i-1}=a_l) = p_{jl}$.
3. Если $x_i=S$, генерация прекращается, и результатом является $x_1x_2...x_{i-1}$.

Дан набор строк, сгенерированных из смеси двух описанных моделей с различными параметрами. Необходимо для каждой строки дать индекс цепи, из которой она была сгенерирована.

В первой строке записано два числа $1000 \le N \le 2000$ и $3 \le K \le 27$ — число строк и размер алфавита, соответственно.

Во второй строке записана строка, состоящая из $K-1$ различных строчных букв латинского алфавита, обозначающая первые $K-1$ элементов алфавита $\mathcal{A}$.

Каждая из следующих $N$ строк сгенерирована по описанному в условии алгоритму.

Гарантируется, что число строк, сгенерированных каждой моделью, составляет не менее $20\%$ от общего числа.

строк, в $i$-ой строке содержится номер кластера (0/1) для последовательности на $i+1$-ой строке входного файла. Совпадение с истинным ответом должно быть не менее $80\%$.

Замечание к тесту из условия: в нём первые 50 строк сгенерированы из распределения $P(x_i = a | x_{i-1}=a) = 0.5, P(x_i = S | x_{i-1}=a) = 0.5, P(x_1=a) = 1$; вторые 50 — из распределения $P(x_i = b | x_{i-1}=b) = 0.5, P(x_i = S | x_{i-1}=b) = 0.5, P(x_1=b) = 1$.