【LC总结】KMP * Implement Strstr

snowell 发布于2019-08-14 15:52 / 802人阅读

摘要：建立长度与目标串相等的模式函数初始化，为，之后，若不重复，赋，若有重复段，赋对应的模式函数值不难，建议死记硬背根据模式函数用两个指针比较两个字符串，当目标串指针和目标串长度相等时，返回差值。

Implement strStr() Problem

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Note

建立长度与目标串相等的模式函数c；
初始化c，c[0]为-1，之后，若不重复，赋0，若有重复段，赋对应的模式函数值（不难，建议死记硬背）；
根据模式函数用两个指针比较两个字符串，当目标串指针和目标串长度相等时，返回index差值。

Solution

public class Solution {
    public int strStr(String a, String b) {
        if (b == null) return 0;
        if (a.length() < b.length()) return -1;
        int m = a.length(), n = b.length();
        int i = -1, j = 0;
        int[] next = new int[n];
        if (next.length > 0) next[0] = -1;
        while (j < n-1) {
            if (i == -1 || b.charAt(i) == b.charAt(j)) next[++j] = ++i;
            else i = -1;
        }
        i = 0; j = 0;
        while (i < m && j < n) {
            if (j == -1 || a.charAt(i) == b.charAt(j)) {
                i++; j++;
            }
            else j = next[j];
        }
        if (j == n) return i-j;
        return -1;
    }
}

海外云主机私有云 Implement strstr mb_strstr KMP

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66070.html

[LintCode] strStr [KMP & brute force]

Problem For a given source string and a target string, you should output the first index(from 0) of target string in source string. If target does not exist in source, just return -1. Note 我终于找到了比较好的K...

Donald 2019-08-14 15:14 评论0 收藏0
[Leetcode] Implement strStr() 实现StrStr

摘要：最新更新暴力法复杂度时间空间思路本题有很多高级算法可以在时间内解决问题，然而这已经超出面试的范畴。本题在面试中出现的作用就是考察基本的编程素养，以及边界条件的考虑。它使用一个数组，这个数组记录了模式串自身的前缀和后缀的重复情况。 Implement strStr() 最新更新：https://yanjia.me/zh/2019/02/... Implement strStr().Re...

remcarpediem 2019-08-14 12:26 评论0 收藏0
LeetCode 28：实现strStr() Implement strStr()

摘要：爱写作者爱写实现函数。说明当是空字符串时，我们应当返回什么值呢这是一个在面试中很好的问题。对于本题而言，当是空字符串时我们应当返回。这与语言的以及的定义相符。利用内建函数直接得结果。如果子字符串为空，返回。爱写bug（ID：icodebugs）作者：爱写bug 实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符...

alaege 2019-08-16 18:31 评论0 收藏0
LeetCode 28：实现strStr() Implement strStr()

摘要：爱写作者爱写实现函数。说明当是空字符串时，我们应当返回什么值呢这是一个在面试中很好的问题。对于本题而言，当是空字符串时我们应当返回。这与语言的以及的定义相符。利用内建函数直接得结果。如果子字符串为空，返回。爱写bug（ID：icodebugs）作者：爱写bug 实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符...

ivydom 2019-07-31 11:26 评论0 收藏0
leetcode 28 Implement strStr()

摘要：如果存在，返回子字符串的在长字符串的起始点的位置。如果不存在，则返回。就是遍历长字符串，并通过比较字符找到是否存在目标子字符串。需要注意一下的就是对特殊情况的判断，以减少无谓的时间消耗。题目详情 Implement strStr().Return the index of the first occurrence of needle in haystack, or -1 if nee...

Gemini 2019-08-15 14:16 评论0 收藏0