有没有类似于PosEx的内置Delphi函数，可以从字符串的末尾开始查找子字符串？

Question

是否有类似于 PosEx 的函数可以在 Delphi D2010 中查找从字符串结尾处开始的子字符串？

我正在移除对 FastStrings 库的所有调用，而我正在使用的一个函数是 FastPosBack：

function FastPosBack(const aSourceString, aFindString : AnsiString; const aSourceLen, aFindLen, StartPos : Integer) : Integer;

我找到了LastDelimiter，但它并不完全相同，因为它只能找到最后一个定界符，而我无法指定起始位置。

谢谢！

更新：根据DR的评论，我创建了这个函数：

function FastPosBack(const aSourceString, aFindString : String; const aSourceLen, aFindLen, StartPos : Integer) : Integer;
var
  RevSourceString, RevFindString: string;
begin
  RevSourceString := AnsiReverseString(aSourceString);
  RevFindString := AnsiReverseString(aFindString);

  Result := Length(aSourceString) - PosEx(RevFindString, RevSourceString, StartPos) + 1;
end;

有没有更有效的方法？在1000000个循环中，Pos需要47毫秒，而FastPosBack需要234毫秒才能完成。

- smartins

---

只是出于好奇，你的测试看起来像什么样子？ - jpfollenius

我调用GetTickCount函数，随后进行1000000次循环调用该函数，并获取差值，即GetTickCount - TickCount。 - smartins

我更感兴趣的是你用于测试的字符串参数。 - jpfollenius

对于 SourceString "dfkfkL%&/s"#<.676505" 和 SearchString "#<", 这是要搜索的非常小的字符串。 - smartins

我认为任何复制整个字符串的函数都不能被视为“快速”。 - Marco van de Voort

Answer 1

尝试使用以下方法：

function RPos(const aSubStr, aString : String; const aStartPos: Integer): Integer; overload;
var
  i: Integer;
  pStr: PChar;
  pSub: PChar;
begin
  pSub := Pointer(aSubStr);

  for i := aStartPos downto 1 do
  begin
    pStr := @(aString[i]);
    if (pStr^ = pSub^) then
    begin
      if CompareMem(pSub, pStr, Length(aSubStr)) then
      begin
        result := i;
        EXIT;
      end;
    end;
  end;

  result := 0;
end;


function RPos(const aSubStr, aString : String): Integer; overload;
begin
  result := RPos(aSubStr, aString, Length(aString) - Length(aSubStr) + 1);
end;

这个重载函数提供了一种调用RPos并从字符串末尾开始搜索的最有效startpos的方法，而无需自己计算。为了提高效率，当显式指定startpos时不会对其进行检查。

在我的SmokeTest性能测试套件中，这比您的FastPosBack快约20％（顺便说一句，该函数还包含一个“off by one”错误，并且需要一些它实际上不使用的参数）。

- Deltics

---

嗨。谢谢你的函数，确实比我想出来的那个（344ms vs 109ms）快得多。函数上的额外参数是为了让我不需要更改任何FastStrings函数调用，只需用我的函数替换它们。 - smartins

Deltics，你的函数是否支持Unicode？我注意到Marco的函数参数是AnsiStrings，而我将在D2010中使用此代码。 - smartins

它是使用Delphi 2009开发和测试的，所以我相信它对Unicode是“安全”的。但是，它假设String和SubStr包含相同的“有效载荷”类型（即字符串和子字符串都是UTF16或ANSI等）。 - Deltics

我刚刚用一些Unicode特定字符测试了一下，确实可以正常工作。我将接受你的答案，因为它提供了与普通Pos相当的性能，这对我来说已经足够了。再次感谢所有回复。你们是最棒的！ - smartins

Deltics，你有没有一个不区分大小写的类似函数？我将为这个具体问题开一个新的问题，但也许你已经有了一些东西。 - smartins

恐怕不行——我没有“闲置”的例程。这个问题吸引了我的好奇心（我喜欢找到解决这类问题的有效方法），所以我创建了这个程序来看看我得到了什么样的结果——它们足够好，以至于我认为值得分享。 :) 去除大小写敏感性会使问题变得更加困难，特别是如果寻找一个跨 ANSI 和 Unicode 字符串可移植的单一解决方案，但你又再次挑战了我内心的那一部分，所以今晚我会花几分钟时间尝试一下，看我能做多少。 - Deltics

Answer 2

您可以使用Pos与StrUtils库中的ReverseString结合使用。

- Daniel Rikowski

---

感谢您的回复，根据您的提示，我已经创建了一个函数，与迄今为止的其他替代方案相比，速度惊人快。 - smartins

Answer 3

Delphi自带一个函数可以向后搜索，在StrUtils单元中的SearchBuf。它专门用于搜索单词，但可能不会完全符合您的要求。下面我将其封装成与您所需接口匹配的函数。

function FastPosBack(const aSourceString, aFindString: AnsiString;
                     const aSourceLen, aFindLen, StartPos: Integer): Integer;
var
  Source, Match: PAnsiChar;
begin
  Source := PAnsiChar(ASourceString);
  Match := SearchBuf(Source, ASourceLen, ASourceLen, 0,
                     AFindString, [soMatchCase]);
  if Assigned(Match) then
    Result := Match - Source + 1
  else
    Result := 0;
end;

- Rob Kennedy

---

感谢您的回复，Rob。不幸的是，这个函数比我自己写的还要慢，需要1310毫秒才能完成。我已经将AnsiString和PAnsiChar更改为String和PChar，因为这正是我想要实现的目标，即用一个不错的替代品来取代这些超快的AnsiString函数。 - smartins

Answer 4

首先，考虑是否需要优化速度。如果在实际使用中不太可能被调用100,000次，则可以通过反转字符串并使用现有的子字符串搜索来解决。

如果速度是一个问题，有很多好的资源可以编写您自己的算法。在维基百科上查找“字符串搜索算法”以获取灵感。我会在我回到电脑时发布链接和示例算法。我目前正在手机上打字。

更新：

这是我承诺的示例：

function RPOS(pattern: string; text:string): Integer;
var patternPosition,
    textPosition: Integer;
begin
  Result := -1;
  for textPosition := Length(text) downto 0 do
  begin
    for patternPosition := Length(pattern) downto 0 do
      if not (pattern[patternPosition] = (text[textPosition - (Length(pattern) - patternPosition)])) then
        break;
    if patternPosition = 0 then
      Result := textPosition -Length(pattern) + 1;
  end;
end;

这基本上是一个倒置的朴素（暴力）字符串搜索算法。它从模式和文本的末尾开始，向开始处逐步工作。我可以保证它比Delphi的Pos()函数效率低，虽然我不能确定它是否比Pos()-ReverseString()组合更快或更慢，因为我没有测试过。它有一个错误，我还没有找到原因。如果两个字符串相同，它将返回-1（未找到）。

- Kenneth Cochran

---

你可能是对的，除非进行大量迭代，否则这些差异不会被注意到。 - smartins

小的差异很快就会累积起来，在这种情况下所需的程序非常小，因此优化是有意义的，因为进行优化的工作量微不足道，并且这意味着如果将来需要在性能关键代码中使用它，则无需担心。当优化的工作量与收益不成比例时，过早地进行优化是一个错误。在这种情况下，努力是最小的，因此如果可以在不牺牲易用性的情况下实现任何收益，则是合理的，我个人认为。 - Deltics

Kenneth，感谢你的函数。我已经测试过了，它的运行时间是453毫秒，而我的函数是344毫秒。Deltics的函数比我的快了300%，只需要109毫秒。 - smartins

我早有预料。朴素字符串搜索算法以其简单而非速度而著称。实际上，除非您向其中添加不必要的操作，否则它可能是最低效的搜索算法。我使用它只是因为编写它只需要大约5分钟。 - Kenneth Cochran

@Kenneth：根据我的经验，优化代码的复杂度并不总是会增加。有时候，比之前更简单的代码表现得更好。主要因素在于原始程序员的水平如何。 - jachguate

Answer 5

我使用Free Pascal的strutils函数中的RPOS变量：

http://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/rtl/objpas/strutils.pp?view=markup

字符串版本与Deltics的几乎相同，但有一些变体：

以下是翻译：

函数 RPosEX(C:char;const S : AnsiString;offs:cardinal):Integer; 重载；
函数 RPosex (Const Substr : AnsiString; Const Source : AnsiString;offs:cardinal) : Integer; 重载；
函数 RPos(c:char;const S : AnsiString):Integer; 重载；
函数 RPos (Const Substr : AnsiString; Const Source : AnsiString) : Integer; 重载；

它们受 FPC 的 LGPL+链接例外许可证的保护，但由于我编写了它们，现在我将它们发布在 BSD 许可证下。

- Marco van de Voort

---

Marco，我注意到这些函数都使用AnsiStrings，所以我认为它们在D2009/D2010中不兼容Unicode。你知道是否有计划使它们兼容Unicode吗？ - smartins

FPC正在开发Unicode编译器模式。它可能会遵循Turbo Pascal->Delphi相同的模型，即可以根据单元选择默认字符串类型。但是基础语言支持需要一段时间，库的更新需要更长时间。代理字符使Unicode情况变得更加困难，因为大多数文档代理扫描技术是向前工作，而不是向后。 - Marco van de Voort

我不会期望在接下来的一年或一年半内有任何生产就绪的东西。 - Marco van de Voort

Answer 6

在进行搜索之前，可能将aSubstr和aString参数转换为大写或小写可以使Deltics的目的不区分大小写。我认为他让你在调用RPos之前完成这个任务，但也许一个可选参数就可以完成工作。

以下是Deltic的目的应该如何：

function RPos(const aSubStr, aString : String; const aStartPos: Integer;
              const aCaseInSensitive:boolean=true): Integer; overload;
var
  i, _startPos: Integer;
  pStr: PChar;
  pSub: PChar;
  _subStr, _string: string;
begin

 if aCaseInSensitive then
 begin
  _subStr := lowercase( aSubstr );
  _string := lowercase( aString );
 end
 else 
 begin
  _subStr := aSubstr:
  _string := aString;
 end;

 pSub := Pointer(_subStr);

 if aStartPos = -1 then
    _startPos :=  Length(_string) - Length(_subStr) + 1
 else
    _startPos := aStartPos;

 for i := _startPos downto 1 do
 begin
   pStr := @(_string[i]);
   if (pStr^ = pSub^) then
   begin
     if CompareMem(pSub, pStr, Length(_subStr)) then
     begin
       result := i;
       EXIT;
     end;
   end;
 end;

 result := 0;
end;


function RPos(const aSubStr, aString : String; 
              const aCaseInSensitive:boolean=true): Integer; overload;
begin
  result := RPos(aSubStr, aString, Length(aString) - Length(aSubStr) + 1,
                 aCaseInSensitive);
end;

- fduenas

Answer 7

虽然不在标准的RTL中，但在INDY中（根据在线帮助中提供的unit idGlobalProtocols），这是最近Delphi安装程序的一部分：

function RPos(
    const ASub: String, 
    const AIn: String, 
    AStart: Integer = -1
): Integer;

- user187694

---

谢谢回复。这个函数比我想出来的那个慢太多了，它花费了5913毫秒（RPos），而我的只需要234毫秒就能完成。 - smartins