1. 字符串匹配问题

• 给定字符串S，和字符串T，查询T在S中出现的位置即为字符串匹配问题；
  

2. 解决方案

2.1 暴力匹配算法

2.1.1 算法步骤

• 使用双指针，指针i指向S串进行遍历，指针j指向T进行遍历；
• 一旦某时刻S[I]!=T[j]，则说明当前子串不匹配，需要重新开始匹配，即i=i-j+1（S中匹配操作新的起始位置），j=0（T从头开始匹配）；
• 当j=T.length时说明匹配成功；
  

2.1.2 代码实现

package com.northsmile.string;/*** @author NorthSmile* @version 1.0* @date 2023/8/22&1:20* 暴力匹配算法解决字符串匹配问题*/
public class StrMatch {public static void main(String[] args) {String s="abdbcabcdef";String t="abc";System.out.println(match(s,t));}public static int match(String s,String t){if (t.length()>s.length()){return -1;}if (s.equals(t)){return 0;}int i=0,j=0;while (i<s.length()&&j<t.length()){if (s.charAt(i)==t.charAt(j)){i++;j++;}else{i=i-j+1;j=0;}}return j==t.length()?i-j:-1;}
}

2.2 KMP算法

• 暴力匹配算法缺点：匹配过程中，一旦匹配失败，文本串要将当前匹配起点+1作为新的起点，在文本串和模式串长度较大时，性能比较低下；
• 使用KMP算法进行字符串匹配，通过利用字符串的前缀和后缀的最长公共子串，降低不必要的无效匹配操作，可提升匹配速度；
  

2.2.1 算法步骤

2.2.2 next数组计算

• 计算每个位置对应的前缀与后缀最大公共长度，得到最大公共长度表；
• 将最大长度均右移一位，用-1填充第一个位置（如果第一个位置要求0开头，则将此事的next数组元素均+1即可）；
  
  

2.2.2 代码实现

package com.northsmile.string;import java.util.Arrays;/*** @author NorthSmile* @version 1.0* @date 2023/8/22&1:20* KMP算法* 目的：i不回退，j回退到特定的位置*/
public class KMP{public static void main(String[] args) {String str="abdbcabcdef";String pattern="abc";
//        String pattern="abcababcabc";
//        String str="BBC ABCDAB ABCDABCDABDE";
//        String pattern="ABCDABD";
//        String pattern="AAAB";System.out.println(Arrays.toString(calNext(pattern)));System.out.println(match(str,pattern,0));}/*** 从str的pos位置查找pattern* @param str* @param pattern* @param pos* @return*/public static int match(String str,String pattern,int pos){if (str==null||pattern==null){return -1;}if (pattern.length()>str.length()){return -1;}if (pos<0||pos>=pattern.length()){return -1;}if (str.equals(pattern)){return 0;}int[] next=calNext(pattern);// i指向文本串，j指向模式串int i=pos,j=0;while (i<str.length()&&j<pattern.length()){// j=-1表示两个串第一个字符就不匹配if ((j==-1)||str.charAt(i)==pattern.charAt(j)){i++;j++;}else{// 回退jj = next[j];}}return j==pattern.length()?i-j:-1;}// 字符串对应next数组的计算public static int[] calNext(String str){int n=str.length();int[] next=new int[n];next[0]=-1;next[1]=0;for (int i=2,k=next[1];i<n;i++){// k=-1表示前缀和后缀没有公共串if (k==-1||str.charAt(i-1)==str.charAt(k)){next[i]=k+1;k=next[i];}else{k=next[k];i--;}}return next;}
}

3. 真题

3.1 力扣 28. 找出字符串中第一个匹配项的下标

class Solution {public int strStr(String haystack, String needle) {return kmp(haystack,needle);}public int kmp(String str, String pattern){if(str==null||pattern==null){return -1;}if(str.length()==0||pattern.length()==0){return -1;}if(pattern.length()>str.length()){return -1;}if(pattern.equals(str)){return 0;}// 计算模式串的next数组int[] next=getNext(pattern);// 匹配查找int i=0,j=0;while(i<str.length()&&j<pattern.length()){if(j==-1||str.charAt(i)==pattern.charAt(j)){i++;j++;}else{// j回退j=next[j];}}return j==pattern.length()?i-j:-1;}public int[] getNext(String str){int n=str.length();if(n==1){return new int[]{-1};}if(n==2){return new int[]{-1,0};}int[] next=new int[n];next[0]=-1;next[1]=0;// k用于记录i-1位置需要回退的位置int i=2,k=0;while(i<n){if(k==-1||str.charAt(i-1)==str.charAt(k)){next[i]=k+1;k++;i++;}else{// k回退k=next[k];}}return next;}
}

3.2 力扣 459. 重复的子字符串

class Solution {// 字符串匹配public boolean repeatedSubstringPattern(String s) {return kmp(s+s,s,1)!=s.length();}public int kmp(String str, String pattern,int pos){if(str==null||pattern==null){return -1;}if(str.length()==0||pattern.length()==0){return -1;}if(pattern.length()>str.length()){return -1;}if(pattern.equals(str)){return 0;}// 计算模式串的next数组int[] next=getNext(pattern);// 匹配查找int i=pos,j=0;while(i<str.length()&&j<pattern.length()){if(j==-1||str.charAt(i)==pattern.charAt(j)){i++;j++;}else{// j回退j=next[j];}}return j==pattern.length()?i-j:-1;}public int[] getNext(String str){int n=str.length();if(n==1){return new int[]{-1};}if(n==2){return new int[]{-1,0};}int[] next=new int[n];next[0]=-1;next[1]=0;// k用于记录i-1位置需要回退的位置int i=2,k=0;while(i<n){if(k==-1||str.charAt(i-1)==str.charAt(k)){next[i]=k+1;k++;i++;}else{// k回退k=next[k];}}return next;}
}

3.3 NC149 kmp算法

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 计算模板串S在文本串T中出现了多少次* @param S string字符串 模板串* @param T string字符串 文本串* @return int整型*/static int count=0;public int kmp (String S, String T) {kmp(T,S,0);return count;}public void kmp (String s, String p,int pos) {if(s==null||p==null){return;}if(s.length()==0||p.length()==0){return;}if(pos<0||pos>=s.length()){return;}int[] next=getNext(p);int i=pos,j=0;while(i<s.length()&&j<p.length()){if(j==-1||s.charAt(i)==p.charAt(j)){i++;j++;}else{j=next[j];}if(j==p.length()){count++;j=next[j];}}}public int[] getNext(String s){int n=s.length();if(n==1){return new int[]{-1};}if(n==2){return new int[]{-1,0};}int[] next=new int[n+1];next[0]=-1;next[1]=0;int i=2,k=0;while(i<=n){if(k==-1||s.charAt(i-1)==s.charAt(k)){next[i]=k+1;k++;i++;}else{k=next[k];}}return next;}
}

3.4 KMP算法

import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str = in.nextLine();String match = in.nextLine();List<Integer> ans=kmp(str,match,0);if(ans.size()==0){System.out.println(-1);return;}for(int i=0;i<ans.size();i++){System.out.print(ans.get(i));if(i!=ans.size()-1){System.out.print(" ");}else{System.out.println();}}}}public static List<Integer> kmp (String s, String p,int pos) {List<Integer> ans=new ArrayList<>();if(s==null||p==null){return ans;}if(s.length()==0||p.length()==0){return ans;}if(pos<0||pos>=s.length()){return ans;}int[] next=getNext(p);int i=pos,j=0;while(i<s.length()&&j<p.length()){if(j==-1||s.charAt(i)==p.charAt(j)){i++;j++;}else{j=next[j];}if(j==p.length()){ans.add(i-j);j=next[j];}}return ans;}public static int[] getNext(String s){int n=s.length();if(n==1){return new int[]{-1,0};}int[] next=new int[n+1];next[0]=-1;next[1]=0;int i=2,k=0;while(i<=n){if(k==-1||s.charAt(i-1)==s.charAt(k)){next[i]=k+1;k++;i++;}else{k=next[k];}}return next;}
}

参考链接https://www.zhihu.com/question/21923021/answer/769606119，这位博主关于next数组计算讲的很清晰！