字符串匹配问题 ----- Rabin-Karp算法

题意：

• 任意给定一段字符串str（“123abc123abc00abc”）
• 再输入一个关键字key（“abc”）
• 要求返回str中包含key的所有子串的头下标

解法1（暴力法）

思路：

• 以key串长度进行窗口滑动
• str中[startIndex, endIndex]的子串与key相同则匹配

复杂度：窗口在n长度的母串滑动复杂度为O(n)，每次比较m长度子串与key串的复杂度为O(m)，综合来看暴力法复杂度为O(n*m)

    public static ArrayList<Integer> match(String str, String key) {ArrayList<Integer> list = new ArrayList<>();for(int startIndex = 0; startIndex < str.length(); startIndex++) {int endIndex;if((endIndex = startIndex + key.length() -1) > str.length() - 1) break;if(str.substring(startIndex,endIndex + 1).equals(key)) {list.add(startIndex);}}return list;}

解法2（RabinKarp算法 ----- 哈希法）

思路：

• 以key串长度进行窗口滑动
• 使用哈希算法计算出key串的哈希值
• str中[startIndex, endIndex]的子串的哈希值与key串哈希值相同则匹配

复杂度：窗口在n长度的母串滑动复杂度为O(n)，每次比较m长度子串的哈希值与key串哈希值复杂度为O(1)，每次计算m长度子串的哈希值与key串哈希值复杂度为O(m)，综合来看该方法复杂度为O(n*m)

	private static final int seed = 31;public static ArrayList<Integer> match2(String str, String key) {ArrayList<Integer> list = new ArrayList<>();long hashOfKey = hash(key);for (int startIndex = 0; startIndex < str.length(); startIndex++) {int endIndex;if ((endIndex = startIndex + key.length() - 1) > str.length() - 1) break;if (hash(str.substring(startIndex, endIndex + 1)) == hashOfKey) list.add(startIndex);}return list;}// 哈希算法public static long hash(String str) {int hash = 0;for (int i = 0; i < str.length(); i++) {hash = hash * seed + str.charAt(i);}return hash % Long.MAX_VALUE;}

关于哈希算法作用、原理和哈希冲突：

1. 作用：能够唯一表示一个字符串，相同的字符串其哈希值相同，不相同的字符串哈希值一定不同
2. 原理："abc"字符串的哈希值为 $(seed^2 * a + seed^1 * a + seed^0 * a)$% Long.MAX_VALUE，可以理解成一个递推式： $a_{n+1} = seed*a_n + srt(n)$(n=0,1,2,3…)，当n=0时 $a_n=0$
3. 哈希冲突：哈希冲突的意思就是，使用该哈希算法后，可能会出现不同字符串的哈希值也相同，这是有一定概率会出现的误差，本哈希算法计算100万个字符串的哈希值，可能会出现110个左右的冲突数

优化：

• 使用滚动哈希法求出母串中所有key长度的子串的哈希值并保存在一个数组中

    public static ArrayList<Integer> match3(String str, String key) {ArrayList<Integer> list = new ArrayList<>();long[] hashes = hashes(str, key.length());for (int startIndex = 0; startIndex < str.length(); startIndex++) {int endIndex;if ((endIndex = startIndex + key.length() - 1) > str.length() - 1) break;if (hash(key) == hashes[startIndex]) list.add(startIndex);}return list;}public static long[] hashes(String str, int lengthOfKey) {long[] hashes = new long[str.length() - lengthOfKey + 1];hashes[0] = hash(str.substring(0, lengthOfKey));for (int startIndex = 1; startIndex < str.length(); startIndex++) {int endIndex;if ((endIndex = startIndex + lengthOfKey - 1) > str.length() - 1) break;// 滚动哈希算法：本窗口子串哈希值=上一个窗口子串的哈希值 * seed + 本窗口最后一个字符 - 上一个窗口第一个字符*pow(seed,lengthOfKey)hashes[startIndex] = hashes[startIndex - 1] * seed + str.charAt(endIndex) - str.charAt(startIndex - 1) * (long) Math.pow(seed, lengthOfKey);}/* for(int statIndex = 0; statIndex < str.length(); statIndex++) {int endIndex;if((endIndex = statIndex + lengthOfKey -1) > str.length() -1) break;hashes[statIndex] = hash(str.substring(statIndex,endIndex+1));}*/return hashes;}public static long hash(String str) {int hash = 0;for (int i = 0; i < str.length(); i++) {hash = hash * seed + str.charAt(i);}return hash % Long.MAX_VALUE;}