Ограничение алфавита для сопоставления строк конечного состояния

Привет, я запрограммировал алгоритм соответствия строк конечного состояния автомата. Однако я изо всех сил пытаюсь ограничить алфавит только двумя символами. Моя реализация похожа на http://www.sanfoundry.com/cpp-program-perform-finite-state-automaton-based-search/.Ограничение алфавита для сопоставления строк конечного состояния

Переменная NO_OF_CHAR указывает на алфавит программы. Я пытаюсь ограничить это только двумя символами {0,1}, например: 0101001. Если у кого-то есть знания о автоматах с конечным состоянием, будет оценен вход.

источник

2015-03-18 jonn

Итак, что вы сделали во время своей борьбы, чтобы ограничить длину алфавита? Какие результаты вы получили? – CiaPan

Когда я изменяю переменную NO_OF_CHARS на 2, программа имеет ошибку. Я думаю, это связано с тем, что char составляет 256? – jonn

Что значит * моя реализация похожа на *? У вас есть собственный код, или это просто копия того, что находится по этой ссылке? И что вы имеете в виду * у программы есть ошибка *? Какая ошибка? Можете ли вы сузить область в своем коде, где у вас есть ошибка, и показать эту часть? – lurker

Ответ был уже принят, но я отправляю его на основе настойчивости OP в более раннем вопросе на эту тему, что должно быть только 2 возможности.

int TF[][NO_OF_CHARS] представляет собой массив, первоначально размер которого составляет #define NO_OF_CHARS 256. Таким образом, в примере все возможные значения unsigned char могут индексировать его. Когда вы пытаетесь уменьшить количество символов до 2, вы можете индексировать этот массив только на 0 или 1, но если ваши '0' и '1' в сотовой строке являются значениями ASCII, они будут разбивать массив.

На основании того, что эта линия (и, возможно, других) foxing массив со

state = TF[state][txt[i]];

Обратите внимание, что с символами '0' и '1' массив будет проиндексирован 48 и 49. Что вам нужно сделать здесь, и, возможно, в других местах, является

state = TF[state][txt[i] & 1];

смотреть Кроме того, имеются ли какие-либо места, где этот показатель 0 или 1 будет повернут обратно в char. Если это так, вам нужно добавить '0' в индекс массива.

источник

2015-03-18 14:57:17

От О.П. ответа на мои вопросы на ввод программы:

голец текст [] = "0101001010101"; char pattern [] = "1001";

Таким образом, вы даете ему нормальную строку с символами, закодированными в ASCII. FSM использует эти символы для индексирования таблицы состояния и перехода (строка 60.) Символ «0» в вашей строке ввода - это значение int, равное 48, тогда как «1» равно 49. Когда вы объявляете массив из 2-х элементов длинными значения приводят к тому, что выражение выходит далеко за пределы массива и считывает некоторые случайные данные. Это заставляет программу блуждать в непредвиденном направлении и в конечном итоге сбой. Это особый случай Неопределенного Поведения.

Комплект NO_OF_CHAR не менее 49 + 1. (Спасибо, @wildplasser!)

источник

2015-03-18 14:46:58 CiaPan

Исправление: 'Решение: установите NO_OF_CHAR как минимум 49 + 1' – wildplasser

@wildplasser Правильно, плюс один из причин, когда индекс основан на нулевом значении! – CiaPan

Ограничение алфавита для сопоставления строк конечного состояния

ответ

Смежные вопросы