Бит-шаблон в последовательности

Question

Я пытаюсь определить любые существующие битовые шаблоны, которые существуют в 32-битной последовательности. Длина битового паттерна варьируется и может быть от 2 до 32. Например, сколько различных битовых шаблонов существует в следующих данных (11,101,110,1100,1010,11001010,etc) и сколько раз каждый образец повторяется.

Похож на сложную проблему. Любое руководство будет полезно.

1 1 1 1 1 1 0 0 0 0 1 0 0 1 1 1 1 0 0 1 0 1 1 0 1 0 1 1 1 1 1 0 
0 1 1 1 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 
1 1 0 0 0 1 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 1 0 0 1 0 0 0 0 0 1 1 
0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 
0 1 0 0 0 1 0 0 0 0 0 0 1 1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 
1 1 1 0 1 1 1 0 0 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 
1 0 0 0 1 0 0 0 1 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 1 
0 1 1 1 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 
1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 0 0 0 0 1 0 
0 0 1 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 0 0 1 1 0 1 
1 1 1 0 1 1 1 0 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 1 0 1 1 0 1 0 0 
0 1 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 0 1 0 0 0 0 1 0 
0 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 1 0 0 0 0 0 0 0 1 
1 1 0 1 1 0 1 1 1 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 1 0 1 0 1 1 1 
1 1 0 0 0 1 1 1 0 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 1 0 1 1 0 1 0 0 
1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 1 0 1 0 1 0 1 0 0 1 1 0 1 
0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 1 0 0 0 0 0 0 0 1 
1 1 1 1 1 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 
0 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 0 1 1 1 1 
1 1 1 1 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 
0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 0 1 1 0 1 0 1 1 

Есть ли более простой способ написать динамический код для этого?

Заранее благодарю за любую помощь.

Answer 1

очень прямой перебор подход будет выглядеть так:

1. Начните с самого первого бита позиции.
2. Проверьте, не превышает ли текущее положение бита битовую строку битовой строки, если она превышает длину строки бита, перейдите к шагу 6. ​​
3. Проверьте, может ли общая битовая строка формироваться повторением текущего шаблона. Текущий шаблон формируется от первого бита до текущего положения бит.
4. Если можно сформировать битовую строку по текущему шаблону, поместите этот шаблон в набор решений.
5. битовая позиция Увеличение на единицу и перейти к шагу 2.
6. Конец

Answer 2

Интересные задачи. Я не знаю, как решить эту проблему оптимальным и эффективным способом, но вы можете попробовать следующий подход:

• Шаг 1: Generate n-bit Gray Codes и хранить его где-нибудь
• Шаг 2: Выберите для каждого кода из генерироваться список в заданной последовательности с одним из алгоритмов поиска:
  • перебором
  • Кнут-Морриса-Пратта
  • Бойер-Мура
  • Рабина-Карпа
  • другие

Как я уже писал выше, это может быть неэффективным и может занять много времени, чтобы выполнить (особенно, если вы собираетесь идентифицировать каждую последовательность битов до 32), так что вы может попытаться найти лучшее решение.

Answer 3

Простейший подход грубой силы заключается в том, чтобы сдвинуть 2-битное окно над данными, считая найденные 2-битные коды. Затем сдвиньте 3-битное окно, затем ... наконец-то 32-битное окно.

Это не изящно, но все, что вам нужно, это хэш-карта счетчиков (на длину бит) и потенциально много памяти, и у вас есть решение с линейным временем.