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