Нужно улучшить алгоритм обнаружения последовательности

Question

Этот вопрос сложный, поэтому, пожалуйста, задавайте вопросы для объяснения более подробной информации об этом quesiton. (Пс. Im не носителем английский язык, вот почему ...)

вход, что образец последовательность с длиной 34, а выход является результатом части

В настоящем время, у меня есть последовательность образец что длина 3, он может быть выполнен в виде: («результат», что мне нужно)

образец последовательности = результат часть + известная последовательность (я не знаю длину результате часть)

1. результат (длина 34)
2. результат (длина N, N < 34) + известная последовательность (34 - N)

Все эти цифры в последовательности являются случайными.

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

Некоторая справочная информация:

1. У меня есть 10 миллионов это образец последовательности с длиной 34. (10 миллионов зная 34 цифр последовательности случайных чисел от генератора)

2. После того, как я найду результат, мне нужно будет сравнить его на 5-миллионной длине последовательности B и найти, соответствует ли последовательность результатов однозначно по длине где-то.

Мой текущий algrothm заключается в использовании детектор, который является первым 10 цифр известной последовательности, и удалить последовательность после того, как если бы обнаружить detecter последовательность где-то в образце последовательности. Тем не менее, есть еще шанс, что результат содержит часть последовательности внутри известной последовательности. У кого-то есть лучший альтрох?

Большое спасибо! Кроме того, я программирую это под python.

ex.

первое условие:

199010104761700150004736290473629657 == Образец сл

всех результаты и известная часть все тот же

входа:

выхода:

второе условие:

199010104728392817111123995561547659 == образец сл

1990101047 == привести часть

+28392817111123995561547659 ... == известная часть

вход будет : 199010104728392817111123995561547659, 2839281711112399556154765 9 ...

выход я хочу это: 1990101047

Answer 1

Вы можете использовать Knuth–Morris–Pratt algorithm. Фактически вы не найдете подстроку, но вы можете принять во внимание значение i, когда вы достигнете конца строки темы.