KMP(字符串匹配算法 c++实现)

- 日理万妓 2022-02-19 13:47 261阅读 0赞

### OpenJudge:  www.openjudge.cn ###

### 题目链接：[KMP][] ###

描述

### 给两个字符串A、B, 从A中找出第一次出现B的位置。 ###

输入

第一行输入一个整数t，表示测试数据的个数  
  
对于每组测试数据，输入两个字符串S T，S和T中间用一个空格隔开，每组数据占一行。  
  
S,T的长度均不超过20000

输出

对于每组测试数据，输出A中找出第一次出现B的位置，如果A不包含B，输出-1

样例输入

3
    AAAAbAA Ab
    AAABBB BB
    XXXXXX YY

样例输出

3
    3
    -1

c++代码如下：

#include <bits/stdc++.h>
    using namespace std;
    const int MAX_LEN = 20010;
    
    // 递推计算Next数组，模板串为str，模板串长度为len
    void get_next(char str[], int len, int next[])
    {
        int i = 0, j = 0;
        next[0] = -1;
        for (i = 1; i < len; i++) {
            while (j > 0 && str[i] != str[j])
                j = next[j-1];
            if (str[i] == str[j]) j++;
            next[i] = j;
        }
    }
    
    // 在字符串s中匹配字符串t，s长度为len_s，t长度为len_t,t的Next数组为next[],返回t第一次出现的位置
    int find_pattern(char s[], int len_s, char t[], int len_t, int next[])
    {
        int i = 0, j = 0;
        while(i < len_s && j < len_t)
        {
            //匹配字符		
    		if(j == -1 || s[i] == t[j])
    		{
    			j++;
    			i++;
    			
    		}
    		else{
    			   j = next[j];
    		}
    	}
    		
    		if(j == len_t)
    		  return i - j ;
    		else
    		   return -1;
        
    }
    
    int main()
    {
        int cas;
        char s[MAX_LEN], t[MAX_LEN];
        int next[MAX_LEN];
        scanf("%d", &cas);
        while (cas --)
        {
            scanf("%s %s", s, t);
            int len_s = strlen(s);
            int len_t = strlen(t);
            get_next(t, len_t, next);
            printf("%d\n", find_pattern(s, len_s, t, len_t, next));
        }
        return 0;
    }

参考文章；[https://blog.csdn.net/gao506440410/article/details/81812163][https_blog.csdn.net_gao506440410_article_details_81812163]

[KMP]: http://xlxxsjjg.openjudge.cn/20190415kmp/A/
[https_blog.csdn.net_gao506440410_article_details_81812163]: https://blog.csdn.net/gao506440410/article/details/81812163