KMP(文字列マッチングアルゴリズムc++実装)

OpenJudge:  www.openjudge.cn
タイトルリンク:KMP
説明
2つの文字列A,Bを与え,Aから初めてBが現れる位置を探し出す.
入力
最初の行には整数tが入力され、テストデータの個数が各テストデータのセットに対して、2つの文字列S Tが入力され、SとTの間に1つのスペースで区切られ、各グループのデータが1行を占める.S,Tの長さはいずれも20000を超えない
しゅつりょく
各テストデータのセットについて、出力Aで初めてBが現れる位置を探し出し、AがBを含まない場合、出力-1
サンプル入力

3
AAAAbAA Ab
AAABBB BB
XXXXXX YY

サンプル出力

3
3
-1

 
c++コードは以下の通りです.

#include 
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
", find_pattern(s, len_s, t, len_t, next));
    }
    return 0;
}

参考記事https://blog.csdn.net/gao506440410/article/details/81812163