Форум программистов
 
О проблемах с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Ответ
 
Опции темы
Старый 24.03.2014, 18:00   #1
Max Glor
 
Регистрация: 20.02.2014
Сообщений: 4
По умолчанию конечные автоматы и LCS

Пожалуйста помогите, разобраться с тем как работают конечные автоматы в c++. Насколько я понимаю, мне подается файл в формате DOT с конечным автоматом, и мне нужно используя его выполнить поиск приближенного совпадения. Собственно вопрос в этом: нужно ли мне чтото делать с входными данными, или их можно просто преобразовать в конечный автомат?; Как работать с конечным автоматом в с++?
Далее о методе решения задачи. Мне нужно найти приближенно совпадение этого конечного автомата в строке. Желательно использовать метод LCS, но в классическом методе (насколько я понял) сравниваются 2 строки, а с автоматами получаются проблемы... Очень хотелось бы услышать какие-нибудь предложения/советы/ссылки на статьи по реализации данного метода (желательно на русском, ибо с английским пока тяжеловато). Заранее спасибо и надеюсь на вашу помощь.
Max Glor вне форума Ответить с цитированием
Старый 24.03.2014, 19:16   #2
Streletz
Старожил
 
Регистрация: 02.01.2014
Сообщений: 2,824
По умолчанию

Цитата:
ссылки на статьи по реализации данного метода (желательно на русском
Простите, но Вы сами гуглить не пробовали? Или гугл не для Вас?
Русскоязычные материалы по теме конечных автоматов гуглятся с 1го раза.
Вот некоторые из них:
Конечные автоматы в C++
c++ - Конечные автоматы
[C++] Шаблон конечного автомата
Цитата:
метод LCS
А, метод точно называется LCS? С LCC случаем, не перепутали?
Streletz вне форума Ответить с цитированием
Старый 24.03.2014, 21:42   #3
Max Glor
 
Регистрация: 20.02.2014
Сообщений: 4
По умолчанию

Цитата:
Сообщение от Streletz Посмотреть сообщение
Простите, но Вы сами гуглить не пробовали? Или гугл не для Вас?
Русскоязычные материалы по теме конечных автоматов гуглятся с 1го раза.
Вот некоторые из них:
Конечные автоматы в C++
c++ - Конечные автоматы
[C++] Шаблон конечного автомата
А, метод точно называется LCS? С LCC случаем, не перепутали?
Мне нужна не теория о том как сделать конечный автомат, а просто как получить автомат который находится в виде графа в формате DOT, и используя его, выполнить поиск приближенного совпадения при помощи метода LCS (longest common substring), проблема в том, что в классическом методе происходит поиск полностью совпадения части строки, мне же надо еще и учитывать возможность того, что могут быть опечатки типов: лишняя буква, пропущенная буква и не та буква (их максимальное количество задается пользователем).
Max Glor вне форума Ответить с цитированием
Старый 24.03.2014, 21:53   #4
Streletz
Старожил
 
Регистрация: 02.01.2014
Сообщений: 2,824
По умолчанию

Цитата:
LCS (longest common substring)
К сожалению, хотите Вы того или нет, но раз уж решили осваивать IT, в частности программирование, Вам придётся рано или поздно открывать для себя английский язык и поиск информации на нём.
Вот готовые примеры реализации LCS: Algorithm Implementation/Strings/Longest common substring.
Цитата:
в виде графа в формате DOT
Скорее на языке DOT. Здесь с русскоязычными материалами немного полегче: DOT (язык).
Streletz вне форума Ответить с цитированием
Ответ
Купить рекламу на форуме от 7000 рублей в месяц



Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
конечные автоматы и LCS Max Glor Помощь студентам 0 23.03.2014 14:59
Конечные автоматы Настя Силина Паскаль, Turbo Pascal, PascalABC.NET 1 23.09.2013 08:39
Конечные автоматы. junaya.ledy Помощь студентам 2 10.05.2013 19:31
Конечные автоматы Svetinka Помощь студентам 1 02.12.2010 12:06
Конечные автоматы... Arkuz Общие вопросы Delphi 2 06.10.2008 23:36


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS
Скидки на курсы GeekBrains 40%, выбирайте программу для себя