【 声明:版权所有,欢迎转载,请勿用于商业用途。 联系信箱:feixiaoxing @163.com】
前面我们谈到了KMP算法,但是讲的还不是很详细。今天我们可以把这个问题讲的稍微详细一点。假设在字符串A中寻找字符串B,其中字符串B的长度为n,字符串A的长度远大于n,在此我们先忽略。
假设现在开始在字符串A中查找,并且假设双方在第p个字符的时候发现查找出错了,也就是下面的情况:
/*
* A: A1 A2 A3 A4 ... Ap ............
* B: B1 B2 B3 B4 ... Bp ...Bn
* (p)
*/
那么这时候,A有什么选择呢?它可以左移1位,用A2~A(p-1)比较B1~B(p-2),然后再用A(p)~A(n+1)比较B(p-1)~B(n)位;或者左移2位,用A3~A(p-1)比较B1~B(p-3),然后再用A(p)~A(n+2)比较B(p-2)~B(n)位;依次类推,直到左移(p-2)位,用A(p-1)比较B(1),然后再用A(p)~A(p+n-2)比较B(2)~B(n)位。
不知道细心的朋友们发现什么规律没?因为A和B在前面(p-1)个数据是相等的,所以上面的计算其实可以这样看:用A2~A(p-1)比较B1~B(p-2),实际上就是B2~B(p-1)比较B1~B(p-2);用A3~A(p-1)比较B1~B(p-3),实际上就是B3~B(p-1)比较B1~B(p-3);最后直到B(p)和B(1)两者相比较。既然这些数据都是B自身的数据,所以当然我们可以提前把这些结果都算出来的。
那么这么多的选择,我们应该左移多少位呢?
其实判断很简单。假设我们左移1位,发现A2~A(p-1)的结果和B1~B(p-2)是一致的,那么两者可以直接从第(p-1)位开始比较了;如果不成功呢,那么只能左移2位,并判断A2~A(p-1)和B1~B(p-2)的比较结果了,......,这样以此类推进行比较。如果不幸发现所有的数据都不能比较成功呢,那么只能从头再来,从第1位数据依次进行比较了。
不知道讲清楚了没,还没有明白的朋友可以看看下面的代码:
int calculate_for_special_index(char str[], int index)
{
int loop;
int value;
value = 0;
for(loop = 1; loop < index; loop ++){
if(!strncmp(&str[loop], str, (index - loop))){
value = index - loop;
break;
}
}
return (value == 0) ? 1 : (index - value);
}
void calculate_for_max_positon(char str[], int len, int data[])
{
int index;
for(index = 0; index < len; index++)
data[index] = calculate_for_special_index(str, index);
}
当然,上面当然都是为了计算在索引n比较失败的时候,判断此时字符应该向左移动多少位。
char* strstr_kmp(const char* str, char* data)
{
int index;
int len;
int value;
int* pData;
if(NULL == str || NULL == str)
return NULL;
len = strlen(data);
pData = (int*)malloc(len * sizeof(int));
memset(pData, 0, len * sizeof(int));
calculate_for_max_positon((char*)str, len, pData);
index = 0;
while(*str && ((int)strlen(str) >= len)){
for(; index < len; index ++){
if(str[index] != data[index])
break;
}
if(index == len){
free(pData);
return (char*) str;
}
value = pData[index];
str += value;
if(value == 1)
index = 0;
else
index = index -value;
}
free(pData);
return NULL;
}
可能朋友们看到了,上面的strlen又回来了?说明代码本身还有优化的空间。大家可以自己先试一试。
int check_valid_for_kmp(char str[], int start, int len)
{
int index;
for(index = start; index < len; index++)
if('\0' == str[index])
return 0;
return 1;
}
char* strstr_kmp(const char* str, char* data)
{
int index;
int len;
int value;
int* pData;
if(NULL == str || NULL == str)
return NULL;
len = strlen(data);
pData = (int*)malloc(len * sizeof(int));
memset(pData, 0, len * sizeof(int));
calculate_for_max_positon((char*)str, len, pData);
index = 0;
while(*str && check_valid_for_kmp((char*)str, index, len)){
for(; index < len; index ++){
if(str[index] != data[index])
break;
}
if(index == len){
free(pData);
return (char*) str;
}
value = pData[index];
str += value;
if(value == 1)
index = 0;
else
index = index -value;
}
free(pData);
return NULL;
}
(三)、多核查找
多核查找其实不新鲜,就是把查找分成多份,不同的查找过程在不同的核上面完成。举例来说,我们现在使用的cpu一般是双核cpu,那么我们可以把待查找的字符分成两份,这样两份查找就可以分别在两个核上面同时进行了。具体怎么做呢,其实不复杂。首先我们要定义一个数据结构:
typedef struct _STRING_PART
{
char * str;
int len;
}STRING_PART;
接着,我们要做的就是把字符串分成两等分,分别运算起始地址和长度。
void set_value_for_string_part(char str[], int len, STRING_PART part[])
{
char* middle = str + (len >> 1);
while(' ' != *middle)
middle --;
part[0].str = str;
part[0].len = middle - (str -1);
part[1].str = middle + 1;
part[1].len = len - (middle - (str - 1));
}
分好之后,就可以开始并行运算了。
char* strstr_omp(char str[], char data[])
{
int index;
STRING_PART part[2] = {0};
char* result[2] = {0};
int len = strlen(str);
set_value_for_string_part(str, len, part);
#pragma omp parellel for
for(index = 0; index < 2; index ++)
result[index] = strstr(part[index].str, part[index].len, data);
if(NULL == result[0] && NULL == result[1])
return NULL;
return (NULL != result[0]) ? result[0] : result[1];
}
注意事项:
(1)这里omp宏要在VS2005或者更高的版本上面才能运行,同时需要添加头文件#include<omp.h>,打开openmp的开关;
(2)这里调用的strstr函数第2个参数是目标字符串的长度,和我们前面介绍的普通查找函数稍微不一样,前面的函数不能直接使用,但稍作改变即可。
分享到:
相关推荐
字符串查找KMP算法
kmp字符串查找算法 最近复习数据结构,在这备个份
用java查找汉字字符串有多重算法,其中Boyer-Moore是基本算法之一。算法简洁,开发容易,是进行搜索引擎开发的重要算法之一。
字符串相似度算法 字符串相似度算法 字符串相似度算法 字符串相似度算法 相似度 字符串
KMP 模式匹配算法实例 C++源码 字符串查找
基于Qt写了一个字符串加密的算法模块(有源码),并封装成了动态库,有测试用例。实现的加密解密算法是AES加密对称算法和BlowFish。用户可以直接用动态库,也可以用源码编译。
a fast string searching algorithm原文
比Boyer-Moore更快的字符串查找算法
一本全面彻底讲解字符串查找算法的书。 书中讲解了34个字符串查找算法的思想。每个算法都有适用性的描述。每个算法都有逐步推演的例子(图解)。每个算法都有代码(C语言)。每个算法都有复杂度分析。每个算法都有...
关于经典算法--压缩字符串(将字符串内连续重复出现的字符进行压缩),个人的想法
字符串的查找是数据库应用中必不可少的操作,而且每种数据库产品(ORACLE、DB2、SYBASE、MS SQL SERVER、MYSQL等等)也都提供了对应的字符串处理函数,比如...本文介绍了通用固定长度编码格式的字符串查找算法的实现。
数据结构,BF算法,替换字符,查找字符,利用BF算法,一个一个回溯进行比较!~
字符串匹配算法之Horspool算法(英文原版)
字符串匹配算法的演示程序,包括了平凡算法、KMP、RK、BM四种,有界面,统计展示移动和比较次数等信息。
本程序是用C语言编写的实现链式字符串运算的算法。简单,里面的注释很详细,对初学者很实用
运行程序之后输入任意的字符串,将字符串转化成二进制数字字符串,然后利用LZ78算法实现对二进制字符串压缩解压,最后再恢复原来的字符串
字符串相似度比较算法,可比较不同长度的任意两个字符串的相似度,以百分比显示。
字符串的模式匹配算法——KMP的C++实现。
带通配符的字符串匹配算法,带通配符的字符串匹配算法
字符串加密解密算法