欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

实现 strStr()

程序员文章站 2022-05-03 23:42:19
LeetCode刷题记1428. 实现 strStr()题目...

LeetCode刷题记14

28. 实现 strStr()

题目
实现 strStr()
可以暴力也可以KMP,下面放KMP

class Solution {
    public static int[] getNext(String str) {
        char[] chs = str.toCharArray();
        int[] next = new int[chs.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < chs.length - 1) {
            if (k == -1 || chs[j] == chs[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }
        return next;
    }
    public static int KMP(String ts, String ps) {
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0; // 主串的位置
        int j = 0; // 模式串的位置
        int[] next = getNext(ps);
        while (i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) { // 当j为-1时,要移动的是i,当然j也要归0
                i++;
                j++;
            } else {
                j = next[j]; // j回到指定位置
            }
        }
        if (j == p.length) {
            return i - j;
        } else {
            return -1;
        }
    }

    public int strStr(String haystack, String needle) {
        if (needle.equals("")) {
            //不能needle == ""
            return 0;
        } else if (haystack.length() == 0) {
            return -1;
        }
        return KMP(haystack, needle);
    }
}

KMP讲解
我自己还有点迷迷糊糊的,今天一点也看不进去了,挖个坑先。

本文地址:https://blog.csdn.net/weixin_44013557/article/details/109605189