KMP算法

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

示例 1：

输入：haystack = "sadbutsad", needle = "sad"
输出：0
解释："sad" 在下标 0 和 6 处匹配。
第一个匹配项的下标是 0 ，所以返回 0 。

示例 2：

输入：haystack = "leetcode", needle = "leeto"
输出：-1
解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。

最常规直观

直接src 字符串和 des 字符串，一个一个的比较，如果出现不一样，则src 开始位置前移一位，des 字符串从0 位置开始，再次比较，直到 src 字符串结束

    public int strStr(String haystack, String needle) {
        if(haystack==null || needle==null || haystack.isEmpty() || needle.isEmpty())
            return -1;
 
        int len1=haystack.length(),len2=needle.length();
 
        for(int i=0;i
            int j=0;
            for(;j
                if(haystack.charAt(i+j) != needle.charAt(j)){
                    break;
                }
            }
            if(j==len2){
               return i;
            }
        }
        return -1;
    }

KMP 算法

src      >abcdabefgh 

dst      >adcdadf   

当比较到 adcdab 后，就出现了不一样，这个时候从头开始又比较；KMP 算法优化这里；

1、获取 dst 字符串的子串相同前缀后缀长度

子串a同前缀后缀    ->0         f(0)=0

子串ad同前缀后缀  ->0        

子串adc同前缀后缀  ->0

子串adcd同前缀后缀  ->0

子串adcda同前缀后缀  -> a  ->1

子串adcdad同前缀后缀->ad ->2

.......

f(n)=    f(n-1)>0,则比较最后一个字符串和f(n-1)对于字符串的f(n-1)+1 位置是否相等

           f(n-1)=0，则比较最后一个字符串跟首字符串是否相等

KMP 算法，暴力匹配获取子串同前缀后缀长度

字符串 aabaaab

KMP[0]=0
KMP[1]=1
KMP[2]=0
KMP[3]=1
KMP[4]=2
KMP[5]=2
KMP[6]=3
 

    public static void KMP_string(String s,int[] KMP){
        //i 表示字符串字串长度，0~len-1
        for(int i=0;i
            //j 表示从j=1 开始跟字串从k=0开始比较，直到子串结束
            int j=1,k=0;
            for(;j<=i;j++){
                if(s.charAt(k) == s.charAt(j)){//对应位置相等，j、k 下个位置
                    k++;
                    continue;
                }else{
                    //对应位置不相等，字串回到0 位置，跟字串比较的也回退k 个位置
                    j-=k;
                    k=0;
                }
            }
            KMP[i]=k;
        }
    }

使用递归计算KMP，递归使用上一次最长前后缀，这样每次只需要比较最后一个位置字符一次

伤神呀，不过按照自己的理解了，写出来还是比较快

 
    public static void KMP_string(String s,int[] KMP){
        //i 表示字符串字串长度，0~len-1
        for(int i=0;i
            //j 表示从j=1 开始跟字串从k=0开始比较，直到子串结束
            int j=1,k=0;
            if(i==0){
                KMP[i]=0;
                continue;
            }
 
            if(KMP[i-1]>0){
                if(s.charAt(i)==s.charAt(KMP[i-1]))
                    KMP[i]=KMP[i-1]+1;
//                else if (s.charAt(i)==s.charAt(0))
//                    KMP[i]=1;
//                else
//                    KMP[i]=0;
                else{
                    //这个时候将Prefix==>s[0~i-1] 当成子串，目标串（前缀），suffix==>s[len(s[0~i-1])-KMP[i-1],i] 为源串（后缀），
                    // 这个时候要从源串中找到目标串在源串的位置
                    //aabaaab
                    //i=0时候，s[0]="a"
                    //i=1,字符串“aa”    这个时候将Prefix=>s[0~0]="a"  , suffix=>s[1~1]="a"
                    //i=2,字符串“aab”   这个时候将Prefix=>s[0~0]="aa"  , suffix=>s[1~1]="ab",从suffix中找跟Prefix最长匹配
                    //i=3,字符串“aaba”  Prefix=>s[0~0]="aab"   suffix=>s[1~1]="aba"
 
                    //当i=n时，从i=n-1 时匹配的位置开始匹配前缀和后缀，最后一个字符不匹配，那这个时候Prefix 后退到0 位置，
                    // suffix 后退到i=n-1时suffix对应的最长相同前后缀位置，即KMP[n-1]
                    k=0;//refix 后退到0 位置
                    j=i-KMP[i-1];//suffix 后退到上次最长相同前后缀位置
                    /*
                    while(k<=i && j<=i){
                        if(s.charAt(k)==s.charAt(j)){
                            k++;
                            j++;
                        }else{
                            //再次取
                        }
                    }*/
 
 
                    //由于前后缀一样KMP[i-1]个长度一样
                    k+=KMP[i-1];
                    j+=KMP[i-1];
 
 
                    int loop=i-1;
                    k=KMP[loop];
                    j=i;
 
                    while(loop>=0){
                        if(s.charAt(k)==s.charAt(j)){
                            KMP[i]=k+1;
                            break;
                        }else{
                            loop--;
                            if(loop<0){
                                KMP[i]=0;
                            }else {
                                k = KMP[loop];
                            }
                        }
                    }
                }
            }else{
                if (s.charAt(i)==s.charAt(0)){
                    KMP[i]=1;
                }else{
                    KMP[i]=0;
                }
            }
 
        }
    }

116. 填充每个节点的下一个右侧节点指针 - 力扣（LeetCode）

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;
    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/
 
class Solution {
    public Node connect(Node root) {
        setNext(root);
        setLayerNext(root);
        showNode(root);
        return root;
    }
 
    public void setNext(Node root){
        if(root == null) return;
 
        if(root.left != null){
            root.left.next = root.right;
        }
 
        setNext(root.left);
        setNext(root.right);
 
    }
 
    public void setLayerNext(Node root){
        if(root == null) return;
 
        if(root.next != null){
            if(root.right != null && root.next != null){
                root.right.next = root.next.left;
            }
        }
 
        setLayerNext(root.left);
        setLayerNext(root.right);
 
    }
 
    public void showNode(Node root){
 
        Node myNode = root;
        if(root == null) return;
        if(root.next == null){
            System.out.print(root.val);
            System.out.print("#");
        }else{
 
            while(myNode.next != null){
                System.out.print(myNode.next.val);
                myNode = myNode.next;
                if(myNode == null){
                    System.out.print("#");
                }
            }
        }
 
        if(root.left != null){
            showNode(root.left);
        }
    }
 
}