字符串HASH：判断子串

文章目录

字符串HASH：判断子串

字符串HASH

字符串HASH，顾名思义，就是将不同字符串映射成不同数字。
字符串HASH是一个既简单又好写，适用性相当广泛的算法。字符串HASH可以替代KMP算法（字符串模式匹配）、马拉车算法（找回文串）等
我们知道，将不同字符串映射成不同数字并不是一件难事，但如果单独地把一个串映射成数字而不能获得这个串的子串的信息，那么这种映射是低端的。如果能够将一个字符串HASH的同时方便的调取其子串的HASH值，那么很多操作将十分方便。在这里我们使用单HASH方法+自然溢出进行字符串HASH，单HASH方法在求出一个串的Hash后，就可以O(1)求解其子串的Hash值。
在提出单HASH公式之前，我们先看一个10进制数与字符串的例子。考虑一个十进制数x:12345，同时“12345”也是一个字符串，它与数字12345唯一对应。我们将”12345″这个字符串映射到了一个10进制数12345，这就是一种带子串信息的HASH，比如我们要调取子串”345”的HASH值，那么就是：

12345 − 12 ∗ 10^3 = 345

同理，我们可以将由字符组成的字符串也看成是一个数字。我们可以选取一个其他进制的基数base，以及一个合适的模数mod(防止溢出)来进行字符串到数字的映射。例如对于一个字符串”abcde”的HASH值为：

那么要得到S[L~R]表示的子串的HASH值时只需:

我们求HASH(S[1~ i])时，可以根据HASH(S[1~i-1]的值求出。此即单HASH公式：

上述两个公式用10进制的例子来类比就容易理解了
我们若要得到某个串的HASH值，可以开一个数组hs[N],hs[i]保存𝐻𝐴𝑆𝐻 (𝑆 [1~𝑖]) 的值。进行一次遍历处理即可得到。(注意：虽然我们选取了其他进制，但最终计算结果表示依然是10进制数。)
由于在使用单HASH公式时，结果可能会非常大，我们需要考虑处理溢出。防止溢出需要选取一个数进行取模操作，取模是为了将HASH值控制在一个范围内，使其能够被基本类型存储，当然这样就可能会发生碰撞，即同一个数字表示了多个字符串。为了减少碰撞的发生，我们可以采用一个大质数作为模数(比如1e9 + 7)，或者直接对long自然溢出(无需手动取模),或者双模数。在这里我们使用自然溢出方法，即我们用java中的long类型数组保存Hash值，这里有一个比较微妙的地方，在java中，long类型为有符号数，最大值为2 ^ 63 – 1，当大于这个值时，会被解释为负数，HASH值变成了负数，字符串HASH的方法会不会失效了呢？其实并没有，负数对于上述的单HASH公式和求子串HASH值的公式同样适用，不会影响结果，利用long类型进行自然溢出就是将HASH值限制在了long类型能表示的范围内，即-2 ^ 63 ~ 2 ^63 -1。
另外需要注意的一点是，在利用单HASH公式时，对于字符到数字的映射，不要把任意字符对应到数字0，比如假如把a对应到数字0，那么将不能从HASH结果上区分ab和b，一般而言，把a-z对应到数字1-26或者直接使用它们的ascii码。
为了避免冲突，base一般为较大的质数，比如2333、23333等(但注意233333就不是质数了）

问题：

思路：

使用字符串HASH的方法，我们可以枚举出所有S串中长度与T串相等的子串，判断子串的HASH值是否等于T串的HASH值

代码：

import java.util.*;

public class Main {
    static long p = 2333;
    static long[] hash = new long[1000002];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s, t;
        s = scanner.next();
        t = scanner.next();
        int i, n = t.length(), ans = 0;
        long temp, hash2 = 0, pw = 1;
        for (i = 1;i <= s.length();i++) {
            hash[i] = hash[i - 1] * p + (s.charAt(i - 1) - 'a' + 1);
        }
        for (i = 1;i <= n;i++) {
            hash2 = hash2 * p + (t.charAt(i - 1) - 'a' + 1);
            pw *= p;
        }
        for (i = 1;i + n - 1 <= s.length();i++) {
            temp = hash[i + n - 1] - hash[i - 1] * pw;
            if (hash2 == temp) {
                ans++;
            }
        }
        if (ans == 0) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
            System.out.println(ans);
        }
    }
}