实现一个挺高级的字符匹配算法:
给一串很长字符串,要求找到符合要求的字符串,例如目的串:123
1******3***2 ,12*****3 这些都要找出来,其实就是类似一些和谐系统。。。。。
这题的真正意思就是,给你一个目标串,如“123”,只要一个字符串里面同时包含1、2和3,那么这个字符串就匹配了。系统越和谐,说明错杀的可能行也就越大。加入目标串的长度为m,模式串的长度为n,我们很容易想到O(mn)的算法,就是两遍for循环搞定。那么有没有更快的方法呢?
我们考虑问题的时候,如果想时间变得快,有一种方法就叫做“空间换时间”。哈希表是一种比较复杂的数据结构。由于比较复杂,STL中没有实现哈希表,因此需要我们自己实现一个。但由于本题的特殊性,我们只需要一个非常简单的哈希表就能满足要求。由于字符(char)是一个长度为8的数据类型,因此总共有可能256 种可能。于是我们创建一个长度为256的数组,每个字母根据其ASCII码值作为数组的下标对应数组的对应项,而数组中存储的0、1对应每个字符是否出现。这样我们就创建了一个大小为256,以字符ASCII码为键值的哈希表。(并不仅限于英文字符,所以这里要考虑256种可能)。
知道了这点,我们可以构建一个数组来统计模式串中某个字符是否出现,然后在对目标串进行扫描,看看对应的所有位上是否出现,从而判断是否匹配。分析一下复杂度,大概是O(m+n)。
实现代码如下:
-
-
intis_contain(char*src,char*des)
-
{
-
-
constinttableSize=256;
-
inthashTable[tableSize];
-
intlen,i;
-
for(i=0;i<tableSize;i++)
-
hashTable[i]=0;
-
len=strlen(src);
-
for(i=0;i<len;i++)
-
hashTable[src[i]]=1;
-
-
len=strlen(des);
-
for(i=0;i<len;i++)
-
{
-
if(hashTable[des[i]]==0)
-
return0;
-
}
-
return1;
-
}
分享到:
相关推荐
字符串处理- 单模式匹配- 朴素的字符串匹配算法(BF 算法).rar
BF算法--串的朴素模式匹配算法,比较实用的方法
KMP算法,全称Knuth-Morris-Pratt字符串搜索算法,是一种线性时间复杂度的字符串匹配算法。它的主要思想是在发生不匹配时,能知道部分已经匹配的字符序列的后缀和模式串的前缀存在重复,因此可以利用这些信息避免...
用Boyer-Moore实现字符串匹配问题。算法中有坏字符移动表和好后缀移动表的创建方法。代码有注视供参考。
基于C#实现并对比三种基本的字符串匹配算法-RK算法-KMP算法-朴素算法
带通配符的字符串匹配算法,带通配符的字符串匹配算法
曲线对比是地层对比的基础手段。提出了一种基于字符串的曲线对比方法,通过对地质事件的...算法允许在匹配过程跳过一定的字符数,实现了曲线的不连续对比。算法对于地层重复与缺失状况下的地层对比具有很好的适用性。
运用C++实现中文字符的KMP匹配算法,实现关键字搜索
字符串处理- 单模式匹配- MP 算法与 KMP 算法.rar
基于n-gram中英文字符串分割算法实现
大数据-算法-具有完美匹配的图依能量的排序.pdf
高级算法KEY-ibm高级算法KEY-ibm高级算法KEY-ibm高级算法KEY-ibm
大数据-算法-基于车流匹配的技术站列车运行线接续模型及算法研究.pdf
关于经典算法--压缩字符串(将字符串内连续重复出现的字符进行压缩),个人的想法
该算法实现了数字字符的匹配,当数字字符相应的十进制数过大时,为了降低匹配的时间复杂度,使用数论中的模运算优化。
大数据-算法-景象匹配末制导系统的匹配算法研究.pdf
KMP字符串匹配算法,一种快速模式匹配算法
大数据-算法-形状匹配算法研究及应用.pdf
字符串匹配算法之Horspool算法(英文原版)