VPF::Автомат - Форум программистов

SoWa

Дата 9.1.2006, 19:52 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 3
Всего: 74

Задача: Написать на Дельфи/Паскале автомат для любой строки.
Автомат- это система поиска подстроки в строке.

Так вот главная проблемма на мой взгляд- составить этот автомат.
Есть статьи или исходники на эту тему?

--------------------

Всем добра smile

DemoCode

Дата 9.1.2006, 19:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 890
Регистрация: 20.10.2005
Где: Россия

Репутация: 1
Всего: 41

Вот функция заменяет одну подстроку (byt) другой (mot)

Код


function StrReplace(text,byt,mot: string): string;
var
  plats: Integer;
begin
  while pos(byt,text) > 0 do
  begin
    plats:=Pos(byt,text);
    Delete(text,plats,Length(byt));
    Insert(mot,text,plats);
  end;
  Result:=text;
end;

--------------------

Жить стало лучше, жить стало веселей
© И.В. Сталин

SoWa

Дата 9.1.2006, 21:02 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 3
Всего: 74

Это и я знаю, но это не автомат.

--------------------

Всем добра smile

Fin

Дата 9.1.2006, 21:16 (ссылка)

(нет голосов)

Загрузка ...

Дракон->Спать();

Профиль
Группа: Участник
Сообщений: 687
Регистрация: 4.1.2006

Репутация: 1
Всего: 10

Ты имееш виду "Конечные автоматы"?
Правда на сайте ребята в основном используют С http://www.softcraft.ru/
Могу дать свои наработки. Правда тоже на си. Я правда использую чуть другую логику отличную от сайтовской.

Это сообщение отредактировал(а) Fin - 9.1.2006, 21:17

--------------------

Пролетал мимо.

Albinos_x

Дата 9.1.2006, 21:21 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 2
Всего: 108

Цитата(SoWa @ 9.1.2006, 19:52

)

Так вот главная проблемма на мой взгляд- составить этот автомат.

не вижу никаких проблем:

Код


// SubStr - строка которую ищем
// Str - строка в которой ищем
// InPos с какой позиции ищем
// возвращяет номер позиции найденой строки или 0
function MyPos(SubStr,Str:string;InPos:integer):Integer;
var Len, SubLen, i : integer;
begin
Result:=0;
// длина строки в которой ищем
Len:=Length(Str);
// длина строки которую ищем
SubLen:=Length(SubStr);
// до какой позиции ищем
Len:=Len-SubLen;
//если длина строки в которой ищем меньше той которой ищем
// то такой строки нет
if (Len-InPos)<SubLen  then
   Exit;
// ищем подстроку в строке с заданной позиции
for i:=InPos to Len do
    if SubStr=copy(Str,i,SubLen) then
       begin
       // если нашли возвращаем результат
       Result:=i;
       Break;
       end;
end;

Добавлено @ 21:28
или может я чего-то не понял?

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

SoWa

Дата 10.1.2006, 08:41 (ссылка)

(нет голосов)

Загрузка ...

Харекришна

Профиль
Группа: Комодератор
Сообщений: 2422
Регистрация: 18.10.2004

Репутация: 3
Всего: 74

Сложность этого алгоритма= Длмнна текста* на длинну строки.
А сложность конечного автомата- длинна текста.
А автомат- это ведь матрица. Надо её составить.

--------------------

Всем добра smile

Albinos_x

Дата 10.1.2006, 11:22 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 2
Всего: 108

эту статью читал:
http://www.rsdn.ru/article/alg/statemachine.xml

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

Albinos_x

Дата 10.1.2006, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Evil Skynet

Профиль
Группа: Комодератор
Сообщений: 3288
Регистрация: 28.5.2004
Где: X-6120400 Y-1 4624650

Репутация: 2
Всего: 108

может тебе так надо:

Код


// SubStr - строка которую ищем    
// Str - строка в которой ищем    
// InPos с какой позиции ищем    
// возвращяет номер позиции найденой строки или 0    
function MyPos(SubStr,Str:string;InPos:integer):Integer;    
var Len, SubLen, i,k : integer;    
begin    
Result:=0;    
k:=0;
// длина строки в которой ищем    
Len:=Length(Str);    
// длина строки которую ищем    
SubLen:=Length(SubStr);    
// ищем подстроку в строке с заданной позиции    
for i:=InPos to Len do    
    begin
    if srt[i]=substr[i mod sublen] then
       k:=k+1
       else
       k:=0;
    if k=sublen then
       begin
       result:=i;
       break;      
       end;
    end;
end;

Это сообщение отредактировал(а) Albinos_x - 10.1.2006, 11:53

--------------------

"Кто владеет информацией, тот владеет миром"
Уинстон Черчилль

Rick

Дата 10.1.2006, 18:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 122
Регистрация: 4.11.2005
Где: Новосибирск

Репутация: 2
Всего: 3

алгоритм Кнута-Морриса-Пратта
http://algolist.manual.ru/search/esearch/kmp.php

алгоритм Бойера-Мура

http://hydra.marketsite.ru/dimas/doc/books...hen/node58.html
http://rsdn.ru/article/alg/textsearch.xml

эти алгоритмы без использования матрицы сравнения, если не подойдут, то могу поискать именно алгоритм приблизительного сравнения с образцом с помощью матрицы

--------------------

Не бывает атеистов в окопах под огнем

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »