Sunday 字符串匹配算法
/*Sunday算法是比较快的匹配算法（据说比KM还快），
算法的主要思想是当父串和字串不匹配时，父串移动尽可能多的字符，提高匹配效率。
比如：
匹配串：O U R S T R O N G X S E A R C H
模式串：S E A R C H
这里我们看到O-S不相同，我们就看匹配串中的O在模式串的位置，没有出现在模式串中。
匹配串：O U R S T R O N G X S E A R C H
模式串： _ _ _ _ _ _ _ _ S E A R C H
移动模式串，使模式串的首字符和O的下一个字符对齐。
匹配串：O U R S T R O N G X S E A R C H
模式串：_ _ _ _ _ _ _ _ S E A R C H
继续比较，N-S不相同，字符R出现在模式串，则后移模式串，将把它们对齐
匹配串：O U R S T R O N G X S E A R C H
模式串： _ _ _ _ _ _ _ _ _ _ _ S E A R C H
例子取自百度百科
代码：
Sunday 字符串模式匹配算法的实现
(如果有两个位置匹配到了，返回第一个位置(位置从0开始算起))
#include <iostream>
#include <string>
using namespace std;
string fat, sun;
int sunday(string fat, string sun) {
int pos = 0;
int len_fat = fat.length();
int len_sun = sun.length();
int fat_move = {0};
//ASCII码一共128个字符，定义数组保存每次失配后主串应移动的距离
for ( int i = 0; i < 128; i++ ) {
fat_move = len_sun + 1;
//先把主串每次失配后移动的距离全部设为最大值
}
for (int j = 0; j < len_sun; j++ ) {
fat_move] = len_sun - j;
//记录子串中每个字符到最右边的距离加一
}
//例如:des = "0124351"
//next = {8 8 8 8 8...7 1 5 4 3 2 8 8 8 8 8 8 8 8 8 8 8 8 8...}
//一开始设定的主串移动距离的最大值会被子串中相同的字符的距离覆盖掉
while (pos <= len_fat - len_sun) {
int i = pos, j = 0;
for ( ; j < len_sun; i++, j++ ) {//子串从0开始比较
if (fat != sun) {
pos += fat_move];
break;
//不匹配主串就移动
}
}
if ( j == len_sun ) {
return pos;//匹配后如果j等于字串的长度，则说明匹配成功
}
}
return -1;
//父串结束后还是未匹配完成则说明子串不存在父串中，返回-1
}
int main() {
getline(cin, fat);
getline(cin, sun);
int pos = sunday(fat, sun);
if ( pos != -1 ) {
cout << pos << endl;
}
else {
cout << "Not found!" << "\n";
}
return 0;
} //Sunday.h : Sunday算法。
//*************************************************************************
//Copyright:
//Author: Sail
//Filename: Sunday string match
//Last Mod time:
//*************************************************************************
//Remarks: Sunday算法是比较快速的字符串匹配算法，比KMP和Booyer-moore算法都
//快，这三种算法都需要提前进行预处理，Booyer-moore是反向比对字符串，Kmp和
//Sunday则是正向比对，各自的预处理方法都不同。
//Sunday算法主要思想是让指向主串的指针在匹配过程中，跳过尽可能多的长度，
//再和模式串进行匹配。平均状况下时间复杂度：O(主串长度/模式串长度)。
//*************************************************************************
#ifndef _my_sunday
#define _my_sunday
#include <string.h>
#include <vector>
using std::vector;
inline void sunday(const char* ori ,const char* pat, vector<int> * res)
{
int i=0;
int j=0;
int olen=strlen(ori);
int plen=strlen(pat);
const int max_size=255;
int * next =new int;
for (i=0;i<max_size;++i)
{
next=plen+1;
}
for (i=0;i<plen;++i)
{
next]=plen-i;
}
i=0;
while(i<=olen-plen)
{
while(j<plen)
{
if (ori!=pat)
{
break;
}
++j;
}
if (j==plen)
{
(*res).push_back(i);
j=0;
}
i+=next];
}
}
#endif
页:
[1]