KMP再探究：next数组的妙用

浏览数：33 / 时间：2015年06月08日

  我们来看一道题目：hihoCoder #1015 : KMP算法

输入

第一行一个整数N，表示测试数据组数。

接下来的N*2行，每两行表示一个测试数据。在每一个测试数据中，第一行为模式串，由不超过10^4个大写字母组成，第二行为原串，由不超过10^6个大写字母组成。

其中N<=20

输出

   对于每一个测试数据，按照它们在输入中出现的顺序输出一行Ans，表示模式串在原串中出现的次数。

样例输入
 
5
HA
HAHAHA
WQN
WQN
ADA
ADADADA
BABABB
BABABABABABABABABB
DAD
ADDAADAADDAAADAAD
 
样例输出
 
3
1
3
1
0
 
实现代码如下：
#include<iostream>
#include<string>
using namespace std;
int sum;//用来记录出现过这样的子串的次数
int GetNext(string t,int *next);
void KMPmatch(string s,string t);
int main(){
  string s,t;//t模式串,s原串
  int n;
  cin>>n;
  while(n--){
    cin>>t>>s;
    sum=0;
    KMPmatch(s,t);
    cout<<sum<<endl;
  }
}
int GetNext(string t,int *next){
    next[0]=-1;
    int i=0,j=-1;
    while(i<t.length()-1){
    if(j==-1||t[i]==t[j]){
        i++;
        j++;
        next[i]=j;
    }
    else
        j=next[j];
    }
}
void KMPmatch(string s,string t){
   int next[100000],i=0,j=0;
   GetNext(t,next);
   while(i<s.length()){
    if(j==-1||s[i]==t[j]){
        i++;
        j++;
    }
    else
        j=next[j];
    if(j==t.length()){
         sum++;
         j--;
         i--;
        j=next[j];//防止漏掉,如：ADADADA,ADA出现了三次
    }
   }

}

每完整匹配一次成功后，就让j=next[j]，为什么这么做，我们通过一个例子就知道。
假设有一个原串S：CABABABDBA，模式串T：ABAB，现在来寻找模式串T在原串S中出现的次数。

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢