Sunday 字符串匹配算法

爱被打了一巴掌 2022-07-24 11:29 134阅读 0赞

/\* 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\[150\] = \{0\};   
//ASCII码一共128个字符，定义数组保存每次失配后主串应移动的距离  
for ( int i = 0; i < 128; i++ ) \{  
fat\_move\[i\] = len\_sun + 1;   
//先把主串每次失配后移动的距离全部设为最大值  
\}  
for (int j = 0; j < len\_sun; j++ ) \{  
fat\_move\[sun\[j\]\] = 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\[i\] != sun\[j\]) \{  
pos += fat\_move\[fat\[pos + len\_sun\]\];  
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;  
\}