常用字符串匹配算法(brute force, kmp, sunday)
2024-08-30 14:55:27
1. 暴力解法
// 暴力求解
int Idx(string S, string T){
// 返回第一个匹配元素的位置,若没有匹配的子串,则返回-1
int S_size = S.length();
int T_size = T.length();
if(S_size == T_size && S_size == )
return ;
if(S_size < T_size)
return -; int head = ;
int i = head;
int j = ; while(i < S_size && j < T_size){
if(S[i] == T[j]){
++i;
++j;
if(j == T_size && i <= S_size)
return head;
}
else{
++head;
i = head;// i回溯, 在kmp算法中,i不会出现回溯,即i值不会减小
j = ;
}
}
return -;
}
2. KMP (包括返回第一个匹配字符串的位置和返回所有匹配字符串的位置)
void PartialMatchTable(string s, int next[]){
int len = s.length();
next[] = -;
int i = ;
int j = -; while(i < len){
if(j == - || s[i] == s[j]){
++i;
++j;
next[i] = j;
}
else
j = next[j];
}
} int kmp(string s, string p){
int s_size = s.length();
int p_size = p.length(); int next[p_size];
PartialMatchTable(p, next);
int i = ;
int j = ;
while(i < s_size && j < p_size){
if(j == - || s[i] == p[j]){
i++;
j++;
}
else{
j = next[j];
}
}
if(j == p_size)
return i-j;
else
return -;
} // kmp_vec(string s, string p)找出所有匹配位置
vector<int> kmp_vec(string s, string p){
int s_size = s.length();
int p_size = p.length();
vector<int> pos; int next[p_size];
PartialMatchTable(p, next);
int i = ;
int j = ;
while(i < s_size && j < p_size){
if(j == - || s[i] == p[j]){
i++;
j++;
if(j == p_size){
pos.push_back(i-j);
j = ;
}
}
else{
j = next[j];
}
} if(pos.size() == )
pos.push_back(-);
return pos;
}
3. Sunday
int SundaySearch(string t, string p){
int t_size = t.size();
int p_size = p.size(); if(p_size <= || t_size <= )
return -; int i = , j = ;
int k;
int m = p_size;
while(i < t_size){
if(t[i] != p[j]) {// 不相等
for(k = p_size-; k>=; --k) {
if(p[k] == t[m])
break;
}
// i = i + p_size - k;
i = m - k;
j = ;
m = i + p_size;
}
else { // 相等,比较下一个字符
i++;
j++;
if(j == p_size)
return i-j;
}
}
return -;
}
4. 完整代码
/*
* @Author: z.c.wang
* @Email: iwangzhengchao@gmail.com
* @Last Modified time: 2019-01-23 14:39:58
*/
#include<iostream>
#include<string>
using namespace std; /**
* 方法1. brute force
* 方法2. KMP (kmp_next, kmp_dfa)
* 方法3. Sunday
*/ /**
* brute_force description:
* 暴力求解,在字符串s中匹配字符串p
* @param t [text, 文本串]
* @param p [pattern, 模式串]
* @return [若s含有p, 则返回第一个匹配的位置,否则,返回-1]
*/
int brute_force(string t, string p){
int t_size = t.length();
int p_size = p.length();
if(t_size == p_size && t_size == )
return ;
if(t_size < p_size)
return -; int head = ;
int i = head;
int j = ;
while(i < t_size && j < p_size){
if(t[i] == p[j]){
i++;
j++;
if(j == p_size && i <= t_size)
return head;
}
else{
head++;
i = head;
j = ;
}
}
return -;
} // 暴力求解的另一种写法
int brute_force2(string t, string p){
int t_size = t.length();
int p_size = p.length(); if(t_size == p_size && t_size == )
return ;
if(t_size < p_size)
return -; int i, j;
for(i = , j = ; i < t_size && j < p_size; i++){
if(t[i] == p[j]){
j++;
}
else{
i -= j;
j = ;
}
}
if(j == p_size) // 找到匹配
return i - j;
else // 为找到匹配
return -;
} /**
* ParticalMatchTable description:
* 对字符串p生成next数组
* @param p [pattern string]
* @param next [next数组]
*/
void ParticalMatchTable(string p, int next[]){
int i = ;
int j = -;
next[] = -; while(i < p.length()){
if(j == - || p[i] == p[j]){
i++;
j++;
next[i] = j;
}
else{
j = next[j];
}
}
} /**
* kmp algorithm based on next
* kmp_next algorithm
* @param t [text string]
* @param p [pattern string]
* @return [若s含有p, 则返回第一个匹配的位置,否则,返回-1]
*/
int kmp_next(string t, string p){
int t_size = t.length();
int p_size = p.length();
int next[p_size];
ParticalMatchTable(p, next); int i = ;
int j = ;
while(i < t_size && j < p_size){
if(j == - || t[i] == p[j]){
i++;
j++;
}
else{
j = next[j];
}
}
if(j == p_size)
return i-j;
else
return -;
} /*kmp algorithm based on dfa */
int kmp_dfa(string t, string p){
int row = ;
int col = p.length(); // 动态分配数组并初始化
int** dfa = new int*[row];
for(int i = ; i < row; i++)
dfa[i] = new int[col];
for(int i = ; i < row ; i++)
for(int j = ; j < col; j++)
dfa[i][j] = ; // 计算dfa
dfa[p[]][] = ;
for (int j = , x = ; j < col; ++j) {
for (int i = ; i < row; ++i)
dfa[i][j] = dfa[i][x];
dfa[p[j]][j] = j + ;
x = dfa[p[j]][x];
} // kmp algo
int i, j;
int t_size = t.length();
int p_size = p.length();
for (i = , j = ; i < t_size && j < p_size; i++){
j = dfa[t[i]][j];
}
if(j == p_size)
return i-j;
else
return -;
} /**
* [Sunday description]
* @param t [description]
* @param p [description]
* @return [description]
*/
int Sunday(string t, string p){
int t_size = t.length();
int p_size = p.length();
if(p_size == t_size && t_size == )
return ;
if(p_size < || t_size < )
return -; int i = ;
int j = ;
int k;
int m = p_size;
while(i < t_size){
if(t[i] != p[j]){
for(k = p_size-; k >= ; --k){
if(p[k] == t[m])
break;
}
i = m - k;
j = ;
m = i + p_size;
}
else{
i++;
j++;
if(j == p_size)
return i-j;
}
}
return -;
} /**
* [main description]
* @param argc [description]
* @param argv [description]
* @return [description]
*/
int main(int argc, char const *argv[])
{
string t = "bbc abcdab abcdabcdabde";
string p = "abcdabd";
// brute force
cout<<"brute_force : "<<brute_force(t, p)<<endl;
// kmp_next
cout<<"kmp_next : "<<kmp_next(t, p)<<endl;
// kmp_dfa
cout<<"kmp_dfa : "<<kmp_dfa(t, p)<<endl;
// Sunday
cout<<"Sunday : "<<Sunday(t, p)<<endl;
cout<<endl;
return ;
}
5. 运行结果
brute_force :
kmp_next :
kmp_dfa :
Sunday :
6. 资料
D.M. Sunday: A Very Fast Substring Search Algorithm. Communications of the ACM
July. 从头到尾彻底理解KMP(2014年8月22日版)
最新文章
- VMware中网络设置之Bridged
- POJ1699 HDU 1560 Best Sequence(AC自动机 最短路)
- 生成并返回 json 结果文件
- 利用 Jquery Deferred 异步你的程序
- mysql更改数据文件目录及my.ini位置| MySQL命令详解
- UVALive 6609 Minimal Subarray Length (查找+构建排序数组)
- bzoj2741【FOTILE模拟赛】L
- Linux网络服务10——远程访问及控制
- 神器Vim之命令介绍
- UESTC 251 最长上升子序列O(nlgn)
- javascript的数组之push()
- Blueking bk 蓝鲸开发环境搭建
- Docker 系列四(自定义仓库).
- HDU 1031(服装打分 **)
- 获取Ueditor里面的图片列表,地址绝对化
- JavaScript学习(三)
- dart基础语法
- linux定时删除文件脚本
- X86和X64环境下的基本类型所占用的字节大小
- NAVICAT 12.0.24 连接 MYSQL8.0.12 的方法
热门文章
- C++笔试题(四)
- hdoj1728【搜索的两种写法】
- springcloud(二) 负载均衡器 ribbon
- 鸟哥私房菜基础篇:Linux 档案与目录管理习题
- 跟我一起玩Win32开发(3):窗口的重绘
- 树状数组 POJ 2481 Cows
- Alt+数字 输入特殊字符
- C. Molly&#39;s Chemicals 暴力 + 统计技巧
- 关于发布WP 8.1应用信息不匹配问题的解决办法
- 解决Android Studio安装过程中“SDK tools directory is missing”的问题