Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > Автомат

Автор: SoWa 9.1.2006, 19:52

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

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

Автор: DemoCode 9.1.2006, 19:58

Вот функция заменяет одну подстроку (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

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

Автор: Fin 9.1.2006, 21:16

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

Автор: Albinos_x 9.1.2006, 21:21

Цитата(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

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

Автор: Albinos_x 10.1.2006, 11:22

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

Автор: Albinos_x 10.1.2006, 11:47

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

Код


// 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;

Автор: Rick 10.1.2006, 18:54

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

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

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

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