繁體中文当前位置: 首页 > 图文教程 > 开发语言 > C/C++ > 子串匹配：不回溯算法
- C/C++
- ActiveX控件中多控制的设计与实现
- 向CCmdTarget的派生类添加一个接口的实现
- 多线程安全的变量模板
- 利用硬件信息实现共享软件的安全注册
- 托管C++程序开发—Win表单文档程序设计(下)
- 在ATL中实现窗口
- 基于Visual C++ 的自动化客户端的实现
- ATL接口映射宏详解
- 托管C++程序开发—Win表单文档程序设计(中)
- 使用Visual C++开发SOAP客户端应用
- Visual C#的SQL Server编程
- VC# .Net中浏览Crystal Report
- 关于GC：Dotnet中Dispose的设计模式
- Visual C++ 优化概述
- Visual C++.NET GDI+编程基础
- .NET 中的断言和跟踪
- 每个开发人员现在应该下载的十种必备工具
- 代码最优化.NET中的内存管理
- 在VC++下对文件属性的获取与更改
- 高手必看：C、C++程序的优化之路
C/C++ 中的 子串匹配：不回溯算法
出处:互联网 整理: 软晨网（RuanChen.com） 发布: 2009-08-14 浏览: 240 ::
收藏到网摘: n/a
子串匹配当然也可以使用不回溯的方式实现，这个算法是笔者在作一个模糊查询的实现的时候想到的，没有确认和通常算法的异同，可能是一个很平常的思想：）。实现的思想很简单：每次比较子串长度的大字符串，若相等则返回，否则在大字符串中的起始位置递进，直到大字符串结束。
实现源码为：
int FindSubString(const char* src,const char* sub)
{
int srcl = strlen(src);
int subl = strlen(sub);
if (subl > srcl)
return -1;
bool HasFound = false;
int l = 0;
int r = subl - 1;
while ((r < srcl) && !HasFound)
{
int i;
for (i = 0; i <= subl - 1; ++i)
{
if (src[i + l] != sub[i])
{
l++;
r++;
break;
}
}
if (i > subl - 1) //找到了
HasFound = true;
}
if (HasFound)
{
return l;
}
return -1;
}
上面实现有一个不好处理的地方就是，当当前大字符串中子串不匹配时候，跳出后不好处理返回标志问题（代码中红色部分），因此可以将对两个相同长度字符串判断相等放到一个函数中实现，则这个实现就更加易于理解：
bool CompareEqual(const char* src,const char* sub,int l)
{
for (int i = 0; i <= l; ++i)
{
if (src[i] != sub[i])
{
return false;
}
}
return true;
}
int FindSubString(const char* src,const char* sub)
{
int srcl = strlen(src);
int subl = strlen(sub);
if (subl > srcl)
return -1;
bool HasFound = true;
int l = 0;
int r = subl - 1;
while (r < srcl)
{
if (CompareEqual(src + l,sub,subl - 1))
{
return l;
}
else
{
l++;
r++;
}
}
return -1;
}
评论 (0) All
