#include<bits/stdc++.h>
#define MAXLEN 255
#define N 255
using namespace std;
typedef struct{
char ch[MAXLEN];
int length;
}SString;
void Init(SString &S, int n){ // 初始化串
for(int i = 1; i <= n ; i ++ ){
cin >> S.ch[i];
}
S.length = n;
}
int Index(SString S, SString T){ // 简单模式匹配 O(mn),但在很多情况下接近O(m + n)
int i = 1, j = 1;
while(i <= S.length && j <= T.length){
if(S.ch[i] == T.ch[j])
i ++, j ++; // 比较后续字符
else
j = 1, i = i - j + 2; // 指针后退
}
if(j > T.length) return i - T.length; // 子串的第一个字符在主串的位置
else return 0;
}
void get_next(SString T, int ne[]){
int i = 1, j = 0;
ne[1] = 0;
while(i < T.length){
if(j == 0 || T.ch[i] == T.ch[j]){
i ++, j ++ ;
ne[i] = j; // ne[j + 1] = ne[j] + 1;
}
else j = ne[j]; // 循环继续
}
}
void get_nextval(SString T, int ne[]){
int i = 1, j = 0;
ne[1] = 0;
while(i < T.length){
if(j == 0 || T.ch[i] == T.ch[j]){
i ++, j ++ ;
if(T.ch[i] != T.ch[j]) ne[i] = j;
else ne[i] = ne[j]; // 再次递归
}
else j = ne[j]; // 循环继续
}
}
int Index_KMP(SString S, SString T, int ne[]){ // 优点:主串不回溯 O(m + n)
int i = 1, j = 1;
while(i <= S.length && j <= T.length){
if(j == 0 || S.ch[i] == T.ch[j])
i ++, j ++; // 比较后续字符
else j = ne[j]; // 模式串向右动
}
if(j > T.length) return i - T.length;
else return 0;
}
int ne[N], n, m;
int main(){
cin >> n >> m; // 串长
SString S, T;
Init(S, n), Init(T, m);
cout << "简单的模式匹配算法结果:" << Index(S, T) << endl;
cout << "next数组:";
get_next(T, ne);
for(int i = 1; i <= m; i ++ ) cout << ne[i] << " "; puts("");
cout << "KMP结果:" << Index_KMP(S, T, ne) << endl;
cout << "nextval数组:";
get_nextval(T, ne);
for(int i = 1; i <= m; i ++ ) cout << ne[i] << " "; puts("");
cout << "改进KMP结果:" << Index_KMP(S, T, ne) << endl;
return 0;
}
/*
测试数据
13 5
a b a b c a b c a c b a b
a b c a c
5 5
a a a b a
a a a a b
*/