ssjssh
diff --git a/‎src/main/java/ssj/algorithm/string/StringUntil.java
Lines changed: 53 additions & 2 deletions b/‎src/main/java/ssj/algorithm/string/StringUntil.java
Lines changed: 53 additions & 2 deletions
diff --git a/‎src/test/java/ssj/algorithm/Main.java
Lines changed: 85 additions & 6 deletions b/‎src/test/java/ssj/algorithm/Main.java
Lines changed: 85 additions & 6 deletions
@@ -165,12 +165,63 @@ public static String compress(String str) {
         return (com_str.length() < str.length()) ? com_str : str;
     }
 
+    /**
+     * kmp算法实现，返回第一个匹配发生的位置
+     *
+     * @param str
+ 
8000
    * @param pattern
+     * @return
+     */
+    public static int search(String str, String pattern) {
+        Preconditions.checkNotNull(str);
+        Preconditions.checkNotNull(pattern);
+        Preconditions.checkArgument(!pattern.isEmpty());
+
+        int[] next_arr = buildNext(pattern);
+
+        for (int cur_index = 0, pattern_index = 0; cur_index < str.length(); cur_index++) {
+            while (pattern_index > 0 && str.charAt(cur_index) != pattern.charAt(pattern_index)) {
+                pattern_index = next_arr[pattern_index - 1];
+            }
+
+            if (pattern.charAt(pattern_index) == str.charAt(cur_index)) {
+                pattern_index++;
+            }
+
+            if (pattern_index == pattern.length()) {
+                return cur_index - pattern_index + 1;
+            }
+        }
 
-    public int search(String str) {
-        //TODO KMP实现字符查找
         return -1;
     }
 
+    /**
+     * 创建数组对应移动表
+     * A  B  C  D  A  B  D
+     * 0  0  0  0  1  2  0
+     * 使用这种表示格式近似表示移动位置，但是在不匹配发生的时候都是用前面元素的位置作为移动
+     * 比如如果最后一个D发送不匹配时，使用B的移动位置也就是2移动
+     *
+     * @param pattern
+     * @return
+     */
+    private static int[] buildNext(String pattern) {
+        int[] result = new int[pattern.length()];
+        for (int cur_index = 2, last_match = 0; cur_index < pattern.length(); cur_index++) {
+            while (last_match > 0 && pattern.charAt(cur_index) != pattern.charAt(last_match)) {
+                last_match = result[last_match];
+            }
+
+            if (pattern.charAt(cur_index) == pattern.charAt(last_match)) {
+                last_match++;
+            }
+
+            result[cur_index] = last_match;
+        }
+        return result;
+    }
+
     /**
      * 要处理变位词需要对输入的单词进行两次排序
      * 1, 按照字母表顺序对每一个串中的字母进行排序
 
@@ -1,18 +1,97 @@
 package ssj.algorithm;
 
-import ssj.algorithm.collections.AVLTree;
+import ssj.algorithm.string.StringUntil;
 
 /**
  * Created by shenshijun on 15/2/1.
  */
 public class Main {
 
     public static void main(String[] args) {
-        int[] data = new int[]{1, 2, 3, 4, 34, 1, 234};
-        AVLTree<Integer> tree = new AVLTree<>();
-        for (int i : data) {
-            tree.add(i);
+        System.out.println(StringUntil.search("BBC ABCDAB ABCDABCDABDE", "ABCDABD"));
+    }
+
+    /**
+     * Returns the index within this string of the first occurrence of the
+     * specified substring. If it is not a substring, return -1.
+     *
+     * @param haystack The string to be scanned
+     * @param needle   The target string to search
+     * @return The start index of the substring
+     */
+    public static int indexOf(char[] haystack, char[] needle) {
+        if (needle.length == 0) {
+            return 0;
+        }
+        int charTable[] = makeCharTable(needle);
+        int offsetTable[] = makeOffsetTable(needle);
+        for (int i = needle.length - 1, j; i < haystack.length; ) {
+            for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
+                if (j == 0) {
+                    return i;
+                }
+            }
+            // i += needle.length - j; // For naive method
+            i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
+        }
+        return -1;
+    }
+
+    /**
+     * Makes the jump table based on the mismatched character information.
+     */
+    private static int[] makeCharTable(char[] needle) {
+        final int ALPHABET_SIZE = 256;
+        int[] table = new int[ALPHABET_SIZE];
+        for (int i = 0; i < table.length; ++i) {
+            table[i] = needle.length;
+        }
+        for (int i = 0; i < needle.length - 1; ++i) {
+            table[needle[i]] = needle.length - 1 - i;
+        }
+        return table;
+    }
+
+    /**
+     * Makes the jump table based on the scan offset which mismatch occurs.
+     */
+    private static int[] makeOffsetTable(char[] needle) {
+        int[] table = new int[needle.length];
+        int lastPrefixPosition = needle.length;
+        for (int i = needle.length - 1; i >= 0; --i) {
+            if (isPrefix(needle, i + 1)) {
+                lastPrefixPosition = i + 1;
+            }
+            table[needle.length - 1 - i] = lastPrefixPosition - i + needle.length - 1;
+        }
+        for (int i = 0; i < needle.length - 1; ++i) {
+            int slen = suffixLength(needle, i);
+
table[slen] = needle.length - 1 - i + slen;            table[slen] = needle.length - 1 - i + slen;
+        }
+        return table;
+    }
+
+    /**
+     * Is needle[p:end] a prefix of needle?
+     */
+    private static boolean isPrefix(char[] needle, int p) {
+        for (int i = p, j = 0; i < needle.length; ++i, ++j) {
+            if (needle[i] != needle[j]) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * Returns the maximum length of the substring ends at p and is a suffix.
+     */
+    private static int suffixLength(char[] needle, int p) {
+        int len = 0;
+        for (int i = p, j = needle.length - 1;
+             i >= 0 && needle[i] == needle[j]; --i, --j) {
+            len += 1;
         }
-        System.out.println(tree);
+        return len;
     }
 }