[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

我终于找到了比较好的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 hereif (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 hereif (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;} }

总结

以上是生活随笔为你收集整理的[LintCode] strStr [KMP brute force]的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。