暴⼒匹配算法和KMP算法介绍

暴⼒匹配算法

现在要判断str1是否含有str2，如果存在，就返回第⼀次出现的位置，如果没有，则返回-1

package ViolenceMatch;
public class ViolenceMatch {
     public static void main(String[] args) {
        String s1 ="BBC ABCDAB ABCDABCDABDE" ;
        String s2 ="太阳和⼩绿" ;
        int m = violence(s1, s2);
        System.out.println(m);
 
    }
 public static int violence(String s1,String s2) {
 
    char a[] = s1.toCharArray();
    char b[] = s2.toCharArray();
    int i =0;
    int j =0;
    while(i<s1.length()&&j<s2.length()) {
        if(a[i]==b[j]) {
            i++;
            j++;
        }else {
            i = i-j+1;
            j =0;
        }
    }
   if(j==s2.length()) {
        return i -j;
    }else {
        return -1;
    }
    }
}

 https://www.cnblogs.com/zzuuoo666/p/9028287.html

package ViolenceMatch;
import java.util.Arrays;
public class KMPAlgorithm {
    public static void main(String[] args) {
        String s1 = "BBC ABCDAB ABCDABCDABDE";
        String s2 = "ABCDABD";
        int next[] = kmpNext("ABCDABD");
        System.out.println("next="+Arrays.toString(next));
        int k = kmpSearch(s1, s2, next);
        System.out.print(k);
    }
    public static int kmpSearch(String s1,String s2,int next[]) {
        for(int i =0,j =0;i<s1.length();i++) {
            while(j>0&&s1.charAt(i)!=s2.charAt(j)) {
                j =next[j-1];
            }
            if(s1.charAt(i)==s2.charAt(j)) {
                j++;
            }
            if(j==s2.length()) {
                return i-j+1;
            }
        }
        return -1;
    }
     public static int[] kmpNext(String dest) {
         int next[] = new int[dest.length()];
         next[0] =0;
         for(int i =1,j=0;i<dest.length();i++) {
             while(j>0&&dest.charAt(i)!=dest.charAt(j)) {
                 j = next[j-1];
             }
             if(dest.charAt(i)==dest.charAt(j)) {
                 j++;
             }
             next[i]= j;
         }
         return next;
     }
}