package newleetcode;/** * leetcode20.strStr匹配字符串 * 给定一个主串和一个匹配字符串 * 在主串中寻找匹配字符串并返回下标 */public class LeetCode28 {//KMP算法 //dp前一个括号代表匹配状态 private int[][] dp; //匹配字符串 private String pat; //kmp算法构造 public LeetCode28(String pat){this.pat=pat; int length=pat.length(); //初始化 dp=new int[length][256]; //状态为0时匹配成功返回1 dp[0][pat.charAt(0)]=1; //影子状态[匹配失败时判断具体回溯][前缀，后缀] int shadow=0; //造字典(通过for循环构造一个匹配字符串字典，目的是通过判断匹配不同字符时字符串如何回溯) for(int j=1;j<length;j++){for(int c=0;c<256;c++){if(pat.charAt(j)==c){//匹配成功时状态进1 dp[j][c]=j+1; }else {//判断当前状态在匹配失败情况下根据c不同返回不同状态 dp[j][c]=dp[shadow][c]; } }//判断前缀后缀，并更新影子状态（不同状态下匹配不同字符会返回相应状态） shadow=dp[shadow][pat.charAt(j)]; } }//kmp算法搜索 public int search(String txt){//初始化匹配字符串状态 int j=0; //for循环，待匹配字符串（主串）永不回溯 for(int i=0;i<txt.length();i++){//计算匹配状态 j=dp[j][txt.charAt(i)]; //匹配成功时返回相应位置 if(j==pat.length())return i-pat.length()+1; }return -1; }//普通搜索方法 public int search1(String pat,String txt){//判断匹配字符串是否为空 if(pat.length()==0)return 0; //判断匹配字符串是否大于主串 if(txt.length()<pat.length())return -1; for (int start=0;start<txt.length()-pat.length()+1;start++){//substring截取字符串进行值匹配，匹配成功返回相应值 if (txt.substring(start,start+pat.length()).equals(pat))return start; }return -1; }//双指针搜索方法 public int search2(String pat,String txt){//判断匹配字符串是否为空 if(pat.length()==0)return 0; //判断匹配字符串是否大于主串 if(txt.length()<pat.length())return -1; int pn=0; while (pn<txt.length()-pat.length()+1){//如果第一个字符不匹配则直接向后匹配,节省匹配时间 while (pn<txt.length()-pat.length()+1&&txt.charAt(pn)!=pat.charAt(0))pn++; //curlen匹配成功长度，pl子串指针 int curlen=0,pl=0; // 