nyoj 5 Binary String Matching （KMP）

向右看齐 2024-02-17 21:12 18阅读 0赞

Binary String Matching  
时间限制：3000 ms | 内存限制：65535 KB  
难度：3  
  
描述  
Given two strings A and B, whose alphabet consist only ‘0’ and ‘1’. Your task is only to tell how many times does A appear as a substring of B? For example, the text string B is ‘1001110110’ while the pattern string A is ‘11’, you should output 3, because the pattern A appeared at the posit  
  
输入  
The first line consist only one integer N, indicates N cases follows. In each case, there are two lines, the first line gives the string A, length (A) <= 10, and the second line gives the string B, length (B) <= 1000. And it is guaranteed that B is always longer than A.  
输出  
For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.  
样例输入  
  
3  
11  
1001110110  
101  
110010010010001  
1010  
110100010101011  
  
样例输出  
  
3  
0  
3  
  
  
这题数据量较小，所以朴素算法也可以A掉，但目的是学习kMP字符串匹配算法，所以，本题我用的KMP算法求解，第一次接触kmp，写起来还是比较棘手…… 其他就不多说了，还是要多练习才有手感。

AC代码：

#include<cstdio>
    #include<cstring>
    using namespace std;
    const int maxn=1000+10;
    char a[12],b[maxn];
    int next[12];
    
    void get_next(){
    	next[0]=0; //next[i]表示对应0~i位置匹配的最长长度 
    	int k=0;  //前后缀匹配最长长度 
    	int len=strlen(a);
    	for(int p=1;p<len;p++){
    		while(k>0 && a[p]!=a[k])
    		k=next[k-1];
    		
    		if(a[p]==a[k]){
    			k++;
    		}
    		next[p]=k;
    	}
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while(T--){
    		scanf("%s%s",a,b);
    		get_next();
            
            int cnt=0;
            int len1=strlen(a);
    		int len2=strlen(b);
    		int i=0,j=0; 
    		
    		while(j<len2){
    			if(a[i]==b[j]){
    				i++;
    				j++;
    			}
    			else if(i==0){  //表示从头开始，无法匹配到，j+1; 
    				j++;
    			}
    			else {
    				i=next[i-1];
    			}
    			
    			if(i==len1){
    				cnt++;
    		        i=next[i-1];
    		   }
    		   
    		}
    		
    		printf("%d\n",cnt);		
    	}
    	return 0;
    }