|
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
|