Быстрое нахождение кол-ва подстрок в строке

← →
IMHO © (2007-04-23 18:10) [0]

... и извлечение N-ой подстроки из строки.

Посоветуйте, плиз, быструю библиотеку для таких операций.

Кол-во подстрок нахожу так:
function SubStrCount(Substr, Str: string): Integer;
var
I: Integer;
begin
Result := 0;
if (Substr = "") or (Str = "") then
Exit;

Substr := UpperCase(Substr);
Str := UpperCase(Str);
I := Pos(Substr, Str);
while I > 0 do
begin
Inc(Result);
Str := Copy(Str, I + Length(Substr), Length(Str));
I := Pos(Substr, Str);
end;
end;

Для извлечения N-ой подстроки из строки использую NPos из RX.

Но все это слишком медленно работает на больших текстовых файлах.

← →
Amoeba © (2007-04-23 18:22) [1]

Посмотри, может что-нибудь быстрое найдется в библиотеке QStrings (бесплатно, в исходниках):
http://www.torry.net/vcl/vcltools/text/adqstrings.zip

← →
Rial © (2007-04-23 19:02) [2]

function SubStrCount(Const SubStr, Str : String; Const bMyFlag : Boolean) : Ineeger;
Var
nP1 : Integer;
nP2 : Integer;
n_P1 : Integer;
nL1 : Integer;
nL2 : Integer;
S1 : String;
S2 : String;
begin
Result:=0;
nL2:=Length(SubStr);
nL1:=Length(Str) - nL2;
If(nL1 < 0) then
Exit;
S1:=UpperCase(Str);
S2:=Uppercase(SubStr);
nP1:=1;
While(nP1 <= nL1) do begin
n_P1 :=nP1;
nP2 :=1;
While(nP2 <= nL2)and(S1[n_P1] = S2[nP2]) do begin
Inc(n_P1);
Inc(nP2);
end;
If(nP2 > nL2) then begin
If(bMyFlag) then nP1 :=nP1 + L2
else Inc(nP1);
Inc(Result);
end else
Inc(nP1);
end;
end;

← →
oxffff © (2007-04-23 21:29) [3]

В Delphi 7 добавили PosEx.

← →
IMHO © (2007-04-23 22:02) [4]

> Rial © (23.04.07 19:02) [2]
>
> function SubStrCount(Const SubStr, Str : String; Const bMyFlag
> : Boolean) : Ineeger;

Гораздо быстрее работает, спасибо!
Как называется этот алгоритм?

← →
Rial © (2007-04-24 01:25) [5]

> [4] IMHO © (23.04.07 22:02)
> Гораздо быстрее работает, спасибо!
> Как называется этот алгоритм?

>>Быстрое нахождение кол-ва подстрок в строке :D

Ты хоть опечатку бы исправил, а то мне 2й раз стыдно стало :)

← →
IMHO © (2007-04-24 09:40) [6]

> Rial © (24.04.07 01:25) [5]

Кстати, на одной строке он неверно подсчитал количество подстрок. Где-то в коде ошибка.

← →
IMHO © (2007-04-24 09:50) [7]

Показал на одну единицу меньше, чем положено было.

← →
Alx2 © (2007-04-24 11:31) [8]

Куча скоростной классики есть на тему поиска подстрок.

Алгоритмы Рабина-Карпа, Кнута-Морриса-Пратта, конечным автоматом.

← →
IMHO © (2007-04-24 11:46) [9]

> Alx2 © (24.04.07 11:31) [8]

Нашел описание Алгоритма Рабина-Карпа, это для поиска подстрок, спасибо.

А для быстрого извлечения N-ой подстроки из строки что посоветуете?

← →
Alx2 © (2007-04-24 11:51) [10]

>IMHO © (24.04.07 11:46)

Его же. В этом алгоритме можно не прерывать поиск в случае обнаружения, а увеличивать счетчик обнаружений.

А зачем её извлекать? Она на 100% совпадает с той подстрокой, что ты искал :)
Возвращать не Integer, а TIntegerDynArray начальных позиций вхождений: зачем одну и ту же работу делать несколько раз?

>IMHO © (24.04.07 11:46)

Недопонял. Все вхождения этой подстроки нужно удалить из строки?
Если так, то два счетчика. Один - для алгоритма поиска, другой - для перезаписи. Перезаписываем в строку все, что не относится к подстроке.
Будет линейное время работы.

Реализация алгоритма Кнута-Морриса-Пратта. Гарантированное линейное время работы.
http://algolist.manual.ru/search/esearch/kmp.php

> Показал на одну единицу меньше, чем положено было.

А сколько в строке «12121» подстрок «121» ? Может алгоритм построен с такой логичкой, что здесь одна подстрока? На самом деле в данном примере количество подстрок определяется конкретной задачей.

> [14] homm © (25.04.07 10:23)
> > Показал на одну единицу меньше, чем положено было.
>
> А сколько в строке «12121» подстрок «121» ? Может алгоритм
> построен с такой логичкой, что здесь одна подстрока? На
> самом деле в данном примере количество подстрок определяется
> конкретной задачей.

Так и проверил на деле процедуру. Работает она.
А bMyFlag как раз и отвечает за измение этой логики.
Логика... алгоритм... детский сад какой то :)

Быстрое нахождение кол-ва подстрок в строке Найти похожие ветки