Здравствуйте, Arsen.Shnurkov, Вы писали:

К>> твой граф являет собой конечный автомат
AS>И как мне это поможет снизить количество операций?

Мы свели задачу к хорошо известной.

Единственно, что если нужно найти не просто факт "цепочка входит", а конкретное место, — то придётся немножко поколдовать.
Вместо автомата-акцептора возьмём недетерминированный автомат-транслятор Мура (каждой вершине соответствует выход "мы посетили эту вершину").
Результат работы — трансляция цепочки раскрасок в цепочку (в множество цепочек) номеров вершин.

К>> что за задача поиска подграфа?

AS>нискажу, но в качестве примера думаю, что подойдёт поиск куска молекулы в целой молекуле.

Если это обычные молекулы, то наверняка можно подойти укрупнённо — искать не по отдельным атомам, а по группам: аминокислоты, сульфидные мостики (если речь о белках), нуклеотиды и даже их триплеты (если речь идёт о ДНК-РНК), либо циклы, гетероциклы, углеводородные цепочки и т.п.