Совпадение строки; алгоритмический вопрос

[hinst]

Пытаюсь придумать как лучше реализовать следующее:
Чтобы был класс который определяет когда произошло вхождение подстроки в строку, причём символы текста, в котором надо искать подстроку, подаются по одному

Код: Выделить всё

TSearcher = class
public
  constructor Create(aDesired: string);
  function Match(c: Char): Boolean;
end;


При этом у класса будет много раз вызываться метод Match, и он должен вернуть True когда в подстроке он достиг конца искомого слова

Код: Выделить всё

for i := 1 to Length(s) do
  if searcher.Match(s[i]) then
    WriteLN('Found desired str at #', i);


До решения "в лоб", которое заключается в том, чтобы сохранять последние Length(aDesired) символов в поле TSearcher'а и каждый раз "прокручивать" влево буфер, вставлять в конец символ и сравнивать BackLog = Desired я уже додумался, но вычислительная сложность такого решения будет не самая лучшая.
Идеи? предложения? плз

[Дож]

Подойдёт любой алгоритм на основе конечных автоматов
http://algolist.manual.ru/search/esearch/index.php
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BD%D1%83%D1%82%D0%B0_%E2%80%94_%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0_%E2%80%94_%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D0%B9%D0%B5%D1%80%D0%B0-%D0%9C%D1%83%D1%80%D0%B0
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0_%E2%80%94_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0
http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%90%D1%85%D0%BE_%E2%80%94_%D0%9A%D0%BE%D1%80%D0%B0%D1%81%D0%B8%D0%BA

[runewalsh]

Такая идея. Ведём список потенциальных соответствий (ПС) — сколько символов начиная с некоторой позиции уже подошло. С новым символом каждое активное ПС либо убивается сразу, если символ не подошёл, либо удлиняется на 1 и, если длина достигла длины образца, тоже убивается и выставляет результат. А если символ соответствует первому символу образца, открывается новое ПС.

Это если тебе при поиске "ee" в "eeeeee" нужны 5 соответствий, а не 3. Из постановки задачи так и есть, просто если 3, то всё вообще тривиально.

Код: Выделить всё

{$mode objfpc}

type
  TSearcher = class
  public
    constructor Create(aDesired: string);
    function Match(c: Char): Boolean;
  private
    desired: string;
    nTrack: integer;
    track: array of integer;
  end;

  constructor TSearcher.Create(aDesired: string);
  begin
    Assert(aDesired <> '');
    desired := aDesired;
    SetLength(track, length(aDesired) - 1);
    nTrack := 0;
  end;

  function TSearcher.Match(c: Char): Boolean;
  var
    i: integer;
    keep: boolean;
  begin
    result := false;
    for i := nTrack - 1 downto 0 do
    begin
      inc(track[i]);
      keep := c = desired[track[i]];
      if keep and (track[i] = length(desired)) then
      begin
        keep := false;
        result := true;
      end;

      if not keep then
      begin
        track[i] := track[nTrack - 1];
        dec(nTrack);
      end;
    end;

    if c = desired[1] then
      if length(desired) = 1 then result := true else
      begin
        inc(nTrack);
        track[nTrack - 1] := 1;
      end;
  end;

var
  s: TSearcher;
  c: char;

begin
  s := TSearcher.Create('needle');
  try
    for c in 'why should you search a needle in a haystack man' do
    begin
      writeln('put(', c, ') = ', s.Match(c));
    end;
  finally
    s.Free;
  end;
end.

[Kemet]

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