托管型网站/互联网营销的十五种方式

implement strStr()

给的难度是简单...其实也还不是那么简单！主要是能应用到KMP算法。数据结构学过，but 还给老师了！下午又复习了一遍。逛了一圈评论，个个都是人才，说话又好听。

（1.年轻人不讲码德：return haystack.indexOf(needle); 结束~睡觉~保养头发）

（2.一顿暴力猛如虎，一看提交5%）

详解链接：作者：AC_OIer
链接：https://leetcode-cn.com/problems/implement-strstr/solution/shua-chuan-lc-shuang-bai-po-su-jie-fa-km-tb86/
来源：力扣（LeetCode）

个人微改：

import java.util.Scanner;

public class implementStr_Kmp {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        System.out.println("please enter your first string :");
        String a = sc.nextLine();
        System.out.println("please enter your second substring :");
        String b = sc.nextLine();
        int q = str(a,b);
        System.out.println("the index of the substring in your string :"+q);
        sc.close();
    }
    
    static int str(String haystack,String needle) {
        //子串长度为0。
        if(needle.isEmpty()) return 0;
        int m = haystack.length(),n=needle.length();
        //加了一个"哨兵",下标比较日常了一点！
        haystack = " "+haystack;
        needle = " "+needle;
        char s[] = haystack.toCharArray();
        char p[] = needle.toCharArray();
        int next[] = new int[n+1];
        //构造next[]数组。
        for(int i=2,j=0;i<=n;i++) {
            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) return i-n;
        }
        
        return -1;
    }
}

测试结果：

please enter your first string :
hello
please enter your second substring :
ll
the index of the substring in your string :2