一个全字匹配的另类算法

发表于 2007 年 1 月 2 日 作者 糖醋鼻子 — 3 条评论 ↓

如果要从一个字符串中匹配某个指定字符串（即查找指定字符串是否在某个字符串中），那么除了按字符逐个搜索外，还有一个另类通俗的算法。下面请跟我来。

代码如下（仅给出DELPHI的实现）：

function searchStr(beStr, subStr: string): Integer;
var
  oldLength: integer;
  tempStr: string;
begin
  oldLength := Length(beStr);
  tempStr := StringReplace(beStr, subStr, ‘|‘, [rfReplaceAll]);
  if Length(tempStr) <oldLength then
  begin
      Result := Pos(‘|‘, tempStr);
  end
  else
  begin
      Result := -1;
  end;
end;

首先，取得要被搜索的字符串（这里为beStr）的长度

接着，使用StringReplace函数将需要搜索的字符串beStr中指定字符串（这里为subStr）替换为特殊的表示符（这里使用了“|”

最后，判断替换后的字符串是否发生了变化，如果变化说明存在相关匹配，可以使用pos函数来定位此匹配。

这个算法避免了繁杂的字符搜索和位置计算。

‹ 妙用Delphi编译器开关为程序增加便捷的控制台调试/日志窗口

要肉体，还是灵魂？ ›

标签： Coding
文章分类 FK Coding

3 条评论在 “一个全字匹配的另类算法” 上

1. jfjy_0 说道：

   2007 年 1 月 11 日 16:11

   我是随缘，我提出我的一点见解，特殊字符有问题，除非你先用pos中查一下是否有这样的字符，没有才能算是特殊字符

   回复
2. zhmnsw 说道：

   2007 年 1 月 12 日 00:02

   随缘MM说得对
   当然得保证字符串中不存在了，呵呵

   回复
3. xyooyy 说道：

   2007 年 1 月 26 日 02:28

   妈的 为什么不能匿名发了
   草
   最快匹配字符串的代码。。。。哈哈 捧捧场
   南物阿密陀夫
   BYTE *MemSearch(const BYTE *mem, const int memSize, const BYTE *patt, const int pattSize)
   {
   if (memSize &lt;= 0 || pattSize &lt;= 0)
   {
   return 0;
   }

   int i;

   int td[256];
   for (int c=0; c&lt;256; ++c)
   {
   td[c] = pattSize + 1;
   }
   const BYTE *p;
   for (p=patt, i=0; i&lt;pattSize; ++p, ++i)
   {
   td[*p] = pattSize – (p – patt);
   }

   const BYTE *t, *tx = mem;

   while (tx + pattSize &lt;= mem + memSize)
   {
   for (p=patt, t=tx, i=0; i&lt;pattSize; ++p, ++t, ++i)
   {
   if (*p != *t)
   {
   break;
   }
   }
   if (i == pattSize)
   {
   return (BYTE*)tx;
   }
   tx += td[tx[pattSize]];
   }
   return 0;
   }

   回复