Посоветуйте алгоритм разбора строки.

Если Yi — это строки (списки символов), то проще всего сделать регексп (Y1)|(Y2)|(Y3)|...|(Yn). Если Yi — просто списки элементов (а не шаблоны в смысле регэкспов), то можно воспользоваться алгоритмом Ахо-Корасика.

Пример приведи.
Из того, что мне удалось понять, могу предложить такой вариант:
((Y1_1) | (Y1_2) | ... | (Y1_N))((Y2_1) | (Y2_2) | ... | (Y2_N))...((YM_1) | (YM_2) | ... | (YM_N))

Yi - это списки строк.

>Пример приведи.

Например, разбор слова по составу. Есть префикс, корень, интерфикс, суффикс и флексия. Из-за омонимии возможно несколько вариантов разбора. Каждая часть может отсутствовать, а может присутствовать несколько раз (пара суффиксов, к примеру). Ну а если алгоритм сможет разобрать и циркумфикс, будет вообще замечательно.

>Из того, что мне удалось понять, могу предложить такой вариант: ((Y1_1) | (Y1_2) | ... | (Y1_N))((Y2_1) | (Y2_2) | ... | (Y2_N))...((YM_1) | (YM_2) | ... | (YM_N))

Пробовал, не то. При большом количестве вариантов (более 17 тыс) обычные регеспы просто не работают, а grep, к примеру, захавал гиг оперативки при таком "шаблоне" на одном слове и не справился за несколько минут.

Алгоритм аля прологовский бактракинг тоже не катит - очень неэффективный.

>то можно воспользоваться алгоритмом Ахо-Корасика.

Да, на первый взгляд, то, что нужно. Сенкс.

> Пробовал, не то. При большом количестве вариантов (более 17 тыс) обычные регеспы просто не работают

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

А есть ли ч-либо (программа/алгоритм) для построения конечных автоматов по шаблонам? То есть на входе - список допустимых строк, алфавит, термальные и нетермальные символы, а на выходе - готовый автомат?