[LintCode] strStr [KMP & brute force]

Donald 發布于2019-08-14 15:14 / 1843人閱讀

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

云服務器 GPU云服務器 Brute force strstr LintCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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