kmp
1.最长前缀和最长后缀分别是指不包含最后一个和第一个的子串
2.next数组是指一个串的各个子串的最长子串和最长后缀的最长匹配长度,-1表示不匹配,0表示匹配一个,1表示匹配两个,依次类推
3.kmp问题:先求模板串的next数组,再用该next数组与模式串比较时,进行跳跃查找,减小了时间复杂度
时间复杂度 O(n+m)
C++ 代码
import java.util.*;
import java.io.*;
class Main{
static int N = 100010;
static int M = 1000010;
static char[] s = new char[M];
static char[] p = new char[N];
static int[] next = new int[N];
static int n,m;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
String str1 = br.readLine();
for(int i = 1;i <= n;i++) p[i] = str1.charAt(i-1);
m = Integer.parseInt(br.readLine());
String str2 = br.readLine();
for(int i = 1;i <= m;i++) s[i] = str2.charAt(i-1);
for(int i = 2,j = 0;i <= n;i++){ //求next数组(各个子串的相同的最长前缀和最长后缀长度)
while(j != 0 && p[i] != p[j+1]) j = next[j]; //到某一位不匹配,跳回
if(p[i] == p[j+1]) j++;
next[i] = j;
}
for(int i = 1,j = 0;i <= m;i++){ //与模式串比较
while(j != 0 && s[i] != p[j+1]) j = next[j]; //跳回
if(s[i] == p[j+1]) j++;
if(j == n){
bw.write(i-n + " ");
j = next[j];
}
}
bw.flush();
bw.close();
br.close();
}
}