锐客网

  1. 首页 > 生活百科 > it技术 > >

go语言对字符串匹配算法 go字符串处理

IT技术匹配

golang规则表达式之贪心(Greedy)和懒惰(Lazy)匹配法在开始说明贪心(Greedy)和懒惰(Lazy)之前，先解释规则表达式的量词符号(Quantifier Symbols) ， 主要就下表6这个：
简单的说：
举一个例子看两者的差异：
第一种是贪心法，找到"ab"之后一直往后匹配，直到最后一个"c"，所以其输出结果就是"abcabc" 。
第二种是懒惰法，找到"ab"之后一直往后匹配，碰到第一个"c"就停止，所以这个例子里面，能找到两个匹配的子串"abc"和"abc" 。
其实第二种的懒惰法可以用另外一种写法：
就是在"ab"之后对"非-c"的字符实现贪心法匹配，然后再碰到"c"就停止，这样达到同样的结果 。
参考资料：
Greedy and lazy quantifiers
这篇文件比较详细的介绍了贪心法和懒惰法的匹配规则 。
不过从具体应用来看，一种需求往往会有多个表达式的写法，所以对于懒惰法的写法也可以用其他的规则表达式来代替，所以如果你实在搞不清楚懒惰法的用处，也可以不用，只要自己找到新的表达法就行 。
【算法笔记】字符串匹配BF 算法中的 BF 是 Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法：
主串和模式串：
在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串 。我们把主串的长度记作 n，模式串的长度记作 m
我们在主串中，检查起始位置分别是 0、1、2…n-m 且长度为 m 的 n-m 1 个子串，看有没有跟模式串匹配的 。
BF 算法的时间复杂度是 O(n*m)
等价于
比如匹配Google 和Goo 是最好时间复杂度，匹配Google 和ble是匹配失败的最好时间复杂度 。
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特—莫里斯—普拉特算法 。KMP算法主要分为两个步骤：字符串的自我匹配，目标串和模式串之间的匹配 。
看来网上很多的文章，感觉很多的都没有说清楚，这里直接复制阮一峰的内容，讲的很清晰
内容来自
首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符 ， 进行比较 。因为B与A不匹配，所以搜索词后移一位 。
因为B与A不匹配，搜索词再往后移 。
就这样 ， 直到字符串有一个字符，与搜索词的第一个字符相同为止 。
接着比较字符串和搜索词的下一个字符，还是相同 。
直到字符串有一个字符，与搜索词对应的字符不相同为止 。
这时，最自然的反应是 ， 将搜索词整个后移一位，再从头逐个比较 。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置 ， 重比一遍 。
一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB" 。KMP算法的想法是，设法利用这个已知信息 ， 不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率 。
怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table） 。这张表是如何产生的，后面再介绍，这里只要会用就可以了 。
已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的 。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：
因为 6 - 2 等于4，所以将搜索词向后移动4位 。
因为空格与C不匹配，搜索词还要继续往后移 。这时，已匹配的字符数为2（"AB"） ， 对应的"部分匹配值"为0 。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位 。
因为空格与A不匹配 ， 继续后移一位 。
逐位比较，直到发现C与D不匹配 。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位 。
逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成 。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0 ， 再将搜索词向后移动7位，这里就不再重复了 。
下面介绍《部分匹配表》是如何产生的 。
首先，要了解两个概念："前缀"和"后缀" 。"前缀"指除了最后一个字符以外 ， 一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合 。
"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度 。以"ABCDABD"为例，
"部分匹配"的实质是，有时候，字符串头部和尾部会有重复 。比如，"ABCDAB"之中有两个"AB" ， 那么它的"部分匹配值"就是2（"AB"的长度） 。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置 。
BM（Boyer-Moore）算法 。它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP 算法的 3 到 4 倍 。
BM 算法包含两部分，分别是坏字符规则（bad character rule）和好后缀规则（good suffix shift）
未完待续
参考文章：
字符串匹配的Boyer-Moore算法
字符串的模式匹配算法#includeiostream
using namespace std;
void Next(char T[],int next[])
{next[0]=-1;
int j=0,k=-1;
while(T[j]!='\0')
if((k==-1)||(T[j]==T[k]))
{j;
k;
next[j]=k;
}
else k=next[k];
}
int KMP(char S[],char T[])
{int i=0,j=0;
int next[10];
Next(T,next);
while((S[i]!='\0')(T[j]!='\0'))
{if(S[i]==T[j]) {i;j;}
else j=next[j];
if(j==-1)
{ i;j; }
}
if(T[j]=='\0') return(i-j 1);
else return 0;
}
int main()
{char a[100],b[100];
cout"please enter primary string :";
cin.getline(a,100);
cout"please enter substring:";
cin.getline(b,100);
if(KMP(a,b)==0)
cout"not exist!\n";
else cout"location is:"KMP(a,b)endl;
return 0;
}
具体的你自己看吧 。
想找一个解决两个字符串匹配程度的算法 。假设string1="abcde",string2="bcd",则分析逻辑如下：
1. 如果string2长于string1 ， 则不匹配
2. 在string1中顺序查匹配string2中第一个字符的字符，
查到后 ， 如果string1余下的字符串长度小于string2的长度，则不匹配
3. 在上述条件满足时，将string1的下一个字符和string2中的第二个字符匹配，以此类推，一旦有一个不匹配 ， 则不匹配 。回到第2步 ， 查找下一个和string2首字符一致的字符 。
4. 如果string2中的字符全都匹配上 ， 则说明string2中string1中识别出来了 。
golang 正则 regexp包使用 先介绍几种常用的方法：
1、使用MatchString函数或Match函数
regexp.MatchString(pattern string, s string)pattern为正则表达式，s为需要校验的字符串
regexp.Match(pattern string, b []byte) pattern为正则表达式 ， s为需要校验的字符串
它们的作用都是匹配 ， 区别在于参数为字符串和切片
实例如下：
2、使用 Compile函数或MustCompile函数
它们的区别是Compile返回两个参数 Regexp,error类型，而MustCompile只返回 Regexp类型
它们的作用是将正则表达式进行编译 ， 返回优化的 Regexp 结构体 ， 该结构体有需多方法 。
实例如下：
3、查找正则匹配字串（ 注：函数名包含string的所传参数为string 其他的均为[]byte带All是所有）
查找正则匹配的字符串位置（ 注：函数名包含string的所传参数为string 其他的均为[]byte带All是所有）
4、替换
正则替换
按原文替换
函数处理替换源字串
5、Regexp结构体中一些常用的方法
算法基础 - 朴素模式匹配算法、KMP模式匹配算法假设我们要从 主字符串goodgoogle 中匹配子字符串google
朴素模式匹配算法就是 通过从主字符的头部开始 一次循环匹配的字符串的挨个字符如果不通过则主字符串头部位置遍历位置 1在依次遍历子字符串的字符
匹配过程
主字符串从第一位开始 取出g子字符串取出第一位 g匹配进入子循环
取出o取出o匹配
取出o取出o匹配
取出d取出g不匹配主字符串遍历位置 1
主字符串从第二位开始 取出o子字符串取出第一位 g不匹配主字符串遍历位置 1
主字符串从第三位开始 取出o子字符串取出第一位 g不匹配主字符串遍历位置 1
主字符串从第四位开始 取出d子字符串取出第一位 g不匹配主字符串遍历位置 1
主字符串从第五位开始 取出g子字符串取出第一位 g匹配进入子循环
取出o取出o匹配
取出o取出o匹配
取出g取出g匹配
取出l取出l匹配
取出e取出e匹配子循环结束匹配成功
假设主字符串 长度为n子字符串长度为mn= m
最好的情况需要匹配m次时间复杂度为 0(m)
例如000000000001匹配00001 每次进入子循环之后 都要遍历到最后一次子循环才得出不匹配
需要匹配次数(n-m 1) * m
最坏的情况需要匹配m次时间复杂度为 0((n-m 1) * m)
KMP 算法的主要核心就是子字符串在子循环内得出不匹配时主字符串当前的判断位不需要回溯–也就是不可以变小 ，且子循环的判断位需要回溯 回溯位与子字符串本身是否具有重复结构有关。以此来规避无效的判断
时间复杂度为 O(n m)
如果主串 S = "abcdefgab"我们要匹配的子串 T = "abcdex"如果用前面的朴素算法，前5个字母完全相同
直到第6个字母f 和 x 不同
步骤1
S: a b c d e f g a b
T: a b c d e x
接下来如果用朴素算法的话那么应该是如下比较
步骤2
S: a b c d e f g a b
T:# a b c d e x
b 和 a 不匹配
步骤3
S: a b c d e f g a b
T: # # a b c d e x
a和c 不匹配
步骤4
S: a b c d e f g a b
T: # # # # a b c d e x
d和a 不匹配
步骤5
S: a b c d e f g a b
T: # # # # a b c d e x
a和e 不匹配
步骤6
S: a b c d e f g a b
T: # # # # # a b c d e x
即主串S中的第2，3 ，4，5，6 位都与子串T的首字符不相等
对于子串T来说如果首字符a与后面的bcdex中任意一个字符都不相等
那么对于上面的第一步来说前五位都相等那么 可以得到 子串首字符a 与主串的第2，3，4，5 位都不相等
即步骤2 ， 3，4，5都是多余的可以直接进入步骤6
如果子串的首字符串与后面的字符有相等的情况
假设S = "abcababca"T= "abcabx"
朴素算法
步骤1
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
步骤2
S: a b c a b a b c a
T:# a b c a b x
b 与 a 不匹配
步骤3
S: a b c a b a b c a
T: # # a b c a b x
c 与 a 不匹配
步骤4
S: a b c a b a b c a
T: # # # a b c a b x
a 与 a 匹配
步骤5
S: a b c a b a b c a
T: # # # # a b c a b x
b 与 b 匹配
步骤6
S: a b c a b a b c a
T: # # # # a b c a b x
a 与 c 不匹配
因为步骤1 中已经得出 前五位已经完全匹配并且子串首字符ab 存在相同的情况所以步骤2，3 是多余的
直接进入步骤4因为步骤1中已经得出主串与子串前五位相同同时 子串1 2 位与 子串的4 5 位相同所以可得出
子串1 2 位 与当前主串匹配位置开始的前两位也就是主串的4 5 位匹配所以步骤4 , 5是多余的可以直接进入步骤6
通过上面的两个例子我们可以发现主串的比较位是不会回溯的，而子串的比较位与子串本身结构中是否有重复相关
子串不重复 举例
S: a b c d e f g a
T: a b c d e x
子串第6位不匹配且本身没有重复那么下一次循环 就变成了 子串的第一位与主串的第二位比较
即子串的匹配位从6 变成了1
S: a b c d e f g a
T:# a b c d e x
子串重复 举例
S: a b c a b a b c a
T: a b c a b x
a 与 x 不匹配
子串在第六位发生不匹配是前五位abcab 具有重复结构ab所以子串匹配位发生变化 即子串的匹配位从6 变成了3
S: a b c a b a b c a
T: # # # a b c a b x
a 与 c 不匹配
我们可以得出 子串匹配位的值 与主串无关 只取决于当前字符串之前的串前后缀的相似度
也就是说 我们在查找字符前 ，要先对子串做一个分析 获取各个位置不匹配时 下一步子串的匹配位
前缀 ：从头开始数不包含最后一位
后缀 :不是倒着数是以和前缀相同的字符串为结尾的部分
例如字符串 a没有前后缀
字符串ab没有前后缀
字符串aba没有前后缀
字符串abab前后缀 ab
字符串ababa前后缀可以是 a可以是 aba我们取长度最长的 即 aba
第一位时 next值固定为0
其他情况 取其公共最长前后缀的长度 1没有则为1
因为一共子串有8位所以在子循环内一共需要获取 8次前后缀
这里我们定义一个next数组长度为8里面的元素分别对应子串各个子循环内的 前后缀长度
第1位不匹配时获取字符串为a没有前字符串没有前后缀那么next[1] = 0
第2位不匹配时获取字符串为ab有前字符串a没有前后缀那么next[2] = 1
第3位不匹配时获取字符串为aba有前字符串ab没有前后缀那么next[3] = 1
第4位不匹配时获取字符串为abab有前字符串aba前后缀 a那么next[4] = 2
第5位不匹配时获取字符串为ababa有前字符串abab前后缀 ab那么next[5] = 3
第6位不匹配时获取字符串为ababaa有前字符串ababa前后缀 aba那么next[6] = 4
第7位不匹配时获取字符串为ababaab有前字符串ababaa前后缀a那么next[7] = 2
第8位不匹配时获取字符串为ababaabc有前字符串ababaab前后缀 ab那么next[8] = 3
next数组为[ 0, 1 , 1 ,2 , 3, 4 ,2, 3 ]
后来有人发现KMP还是有缺陷的比如 当子串 T = "aaaaax"
在5位发生不匹配 此时 next[5] = 4接着就是 子串中的第四位a与 主串当前位置字符比较
因为子串第五位等于子串第四位相同 所以可以得出该步骤也不匹配此时next[4] = 3
依然不匹配直到next[1] = 0
我们可以发现由于T串中的 2 3 4 5 位置都与首位a 相等中间的过程都是多余的
那么可以用首位的next[1] 的值 去替代与它相等的字符后续的next[x]的值
【go语言对字符串匹配算法 go字符串处理】关于go语言对字符串匹配算法和go字符串处理的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：如何创建个性化的云服务器？ 怎么建独有云服务器

    下一篇：oracle数据库修改表，oracle数据库修改表添加字段