给定一个主串 S(长度 <=10^6) 和一个模式 T(长度<=10^5), 要求在主串 S 中找出与模式 T 相匹配的子串, 返回相匹配的子串中的第一个字符在主串 S 中出现的位置.
输入格式:
输入有两行: 第一行是主串 S; 第二行是模式 T.
输出格式:
输出相匹配的子串中的第一个字符在主串 S 中出现的位置. 若匹配失败, 输出 0.
输入样例:
在这里给出一组输入. 例如:
aaaaaba ba
输出样例:
在这里给出相应的输出. 例如:
6
解题思路: 串的模式匹配有两种: 一种是 BF 算法, 一种是 KMP 算法;
基于这道题给的数据, 若用 BF 算法便会超时, 所以我们这道题用 KMP 算法;
那么问题来了, KMP 算法到底怎么用的; 简单来讲, 就是有两个步骤:
1, 求模式串的 next 数组;
2, 进行主串与模式串的匹配;
假设主串和模式串分别为
第一个问题: 如何求 next 数组
??next 数组求的是模式串的!!!
下面就以上面给的模式串为例;
next 数组便是前缀中的最长相同前后缀, 说起来比较绕, 什么意思呢, 模拟一遍就清楚了;
所以对于模式串对应的 next 数组为
这样我们就求出了 next 数组;
接下来进行模式匹配, 其实这样就会有个问题, 所以实际上 next 数组这样是需要改进的;
假设我们不改进的话, 进行匹配会出现什么问题呢;
进行模式匹配的大概代码如下:
1, 即匹配, 则 i++;j++;
2, 不匹配, 根据刚刚求出的 next 数组, 进行跳 next 数组;
下面代码中 ssize 为主串 s 的长度, tsize 为模式串 t 的长度;
下面我们就根据代码模拟一遍;
- int i = 0 ;
- int j = 0;
- while(i<ssize&&j<tsize)
- {
- if(s[i]==t[j])
- {
- i++;
- j++;
- }
- else
- {
- j = next1[j];
- }
- }
- if(j==tsize)
- {
- cout <<i-j+1;
- }
上面我们求出来的 next 数组为:
现在我们把它们的下面也写上:
现在开始模拟一遍:
我们发现匹配到 c 的时候不匹配了, 跳 next 数组, 则跳到下标为 0 处, 变成:
此时也不匹配, 变成应该跳 next 数组, 跳到下标为 0 处, 但是这样就变成死循环了, 所以我们应该退一步, 将 next 数组的第 0 个赋值为 - 1, 且将整个 next 数组向后移; 就不会变成死循环了;
再模拟一次:
此时不匹配跳 next 数组;
变成:
发现 a 不匹配, 跳 next 数组:
继续模拟:
发现不匹配, 所以此时 next 应该跳到下标为 - 1 处, 但是这里没有下标为 - 1 的, 所以实际上就是整体向后移; 变成:
发现完全匹配了;
那么基于上面的改进, next 数组应该怎么写呢:
代码如下:
- string s;
- string t;
- int ssize;
- int tsize;
- int next1[2000000];
- void nextsz(string t,int tsize)
- {
- next1[0] = -1; // 防止进入死循环, 而且到不能匹配时能整体后移
- int k = -1; // 是为了调节 next 数组;
- int j = 0 ;
- while(j < tsize-1)
- {
- if(k==-1||t[j]==t[k]) //k=-1 进入这个循环是为了整体向后移;
- {
++k; k 实际上也是记录了相同的个数;
- ++j;
next1[j] = k; 找到 next 数组;
- }
- else
- k = next1[k]; // 不相同则更新 k;
- }
- }
现在会了 next 数组, 我们则可以进行模式匹配了;
利用上面求的 next 数组来进行模式匹配; 过程原理和上面画的图是一模一样的;
代码如下:
- int kmp(string s,string t,int sszie,int tsize)
- {
- int j = 0;
- int i = 0;
- while(i<ssize&&j<tsize)
- {
if(j==-1||s[i]==t[j]) j=-1 是为了调节到跳无可跳时, 整体向后移;
- {
- i++; // 匹配整体向前移;
- j++;
- }
- else
- {
j = next1[j]; 不断跳 next 数组;
- }
- }
- if(j==tsize)
- {
- return i-j+1; // 返回模式串在主串的第一个下标;
- }
- else return -1; // 不匹配, 则返回 - 1;
- }
所以这道题的完整代码如下:
代码如下:
- #include<iostream>
- #include<string.h>
- using namespace std ;
- string s;
- string t;
- int ssize;
- int tsize;
- int next1[2000000];
- void nextsz(string t,int tsize)
- {
- next1[0] = -1;
- int k = -1;
- int j = 0 ;
- while(j <tsize-1)
- {
- if(k==-1||t[j]==t[k])
- {
- ++k;
- ++j;
- next1[j] = k;
- }
- else
- k = next1[k];
- }
- }
- int kmp(string s,string t,int sszie,int tsize)
- {
- int j = 0;
- int i = 0;
- while(i<ssize&&j<tsize)
- {
- if(j==-1||s[i]==t[j])
- {
- i++;
- j++;
- }
- else
- {
- j = next1[j];
- }
- }
- if(j==tsize)
- {
- return i-j+1;
- }
- else return 0;
- }
- int main()
- {
- cin>>s;
- cin>>t;
- ssize = s.size();
- tsize = t.size();
- nextsz(t,tsize);
- cout<<kmp(s,t,ssize,tsize)<<endl;
- }
(原创)数据结构之利用 KMP 算法解决串的模式匹配问题
来源: http://www.bubuko.com/infodetail-3016497.html