[LintCode] strStr [KMP & brute force]

Donald 发布于2019-08-14 15:14 / 1742人阅读

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

我终于找到了比较好的KMP算法。
http://alice-alicesspace.blogspot.com/2015/07/strstr-kmp-solution-java.html

Solution

class Solution {
    public int strStr(String source, String target) {
        //write your code here
        if (source == null | target == null) {
            return -1;
        }
        int i, j;
        for (i = 0; i < source.length() - target.length() +1; i++) {
            for (j = 0; j < target.length(); j++) {
                if (source.charAt(i+j) != target.charAt(j)) {
                break;
                }
        }
        if (j == target.length()) {
            return i;
        }
        }
        return -1;
        }
}

KMP算法不如也贴出来。

class Solution {
    public int strStr(String source, String target) {
        //write your code here
        if (source == null || target == null) {
            return -1;
        }
        if (target.length() == 0) {
            return 0;
        }
        
        int[] prefix = new int[target.length()];
        int k = 0;
        for (int i = 1; i < target.length(); i++) {
            while (k > 1 && target.charAt(k) != target.charAt(i)) {
                k = prefix[k-1];
            }
            if (target.charAt(i) == target.charAt(k)) k++;
            prefix[i] = k;
        }
        k = 0;
        for (int i = 0; i < source.length(); i++) {
            while (k > 1 && source.charAt(i) != target.charAt(k)) {
                k = prefix[k-1];
            }
            if (target.charAt(k) == source.charAt(i)) {
                k++;
            }
            if (k == target.length()) {
                return i - k + 1;
            }
        }
        return -1;
    }
}

私有云海外云主机 Brute force strstr LintCode

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

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

[LintCode/LeetCode] Two Sum

摘要：就不说了，使用的解法思路如下建立，对应该元素的值与之差，对应该元素的。然后，循环，对每个元素计算该值与之差，放入里，。如果中包含等于该元素值的值，那么说明这个元素正是中包含的对应的差值。返回二元数组，即为两个所求加数的序列。 Problem Given an array of integers, find two numbers such that they add up to a s...

xiaoxiaozi 2019-08-14 15:22 评论0 收藏0
【LC总结】KMP * Implement Strstr

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

snowell 2019-08-14 15:52 评论0 收藏0
[LintCode/LeetCode] Two Strings are Anagrams/Valid

摘要：建立一个长度为的数组，统计所有个字符在出现的次数，然后减去这些字符在中出现的次数。否则，循环结束，说明所有字符在和中出现的次数一致，返回。 Program Write a method anagram(s,t) to decide if two strings are anagrams or not. Example Given s=abcd, t=dcab, return true....

vslam 2019-08-14 15:22 评论0 收藏0
[LintCode/LeetCode] Contains Duplicate III

Problem Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute dif...

MageekChiu 2019-08-19 10:48 评论0 收藏0
DVWA学习之Brute Force

摘要：运行结果片段发现密码的返回长度与其他不同，获得密码，爆破成功。源码分析加入了对登录失败次数做限制，防止爆破用了更为安全的机制防御注入 BurpSuite-Intruder笔记 Burp intruder是一个强大的工具，用于自动对Web应用程序自定义的攻击。它可以用来自动执行所有类型的任务您的测试过程中可能出现的模块说明 Target 用于配置目标服务器进行攻击的详细信息 Posi...

Near_Li 2019-07-31 10:31 评论0 收藏0