假設(shè)我們輸入兩個字符串s1、s2武翎，其中s1的長度必須大于等于s2長度佣盒。我們要求出s2在s1中出現(xiàn)了多少次。
例如：
輸入樣例
abcaabcaabcbcabc
abc
輸出樣例
4
2、算法原理
? 這道題如果采用枚舉暴力的方法時間復(fù)雜度會達到O(mn)。枚舉方法的思路很簡單么伯，利用2個指針從頭到尾掃描2個字符串：
//枚舉
private static void solve01(String s1, String s2) {
int len_s1 = s1.length();
int len_s2 = s2.length();
int ans = 0;//記錄答案
for(int i = 0; i < len_s1; i++) { //掃描s1字符串
if(s1.charAt(i) == s2.charAt(0)) {//當s2第一個字符與s1字符串的第一個字符匹配上的時候
int j = 0;
for(j = 1; j < len_s2; j++) {//利用第二個指針控制兩個字符串的下標驗證是否滿足要求
if(s1.charAt(i + j) != s2.charAt(j)) { //不滿足則退出循環(huán)
break;
}
}
if(j == len_s2) { //當j == len_s2的時候則說明第二個循環(huán)從頭掃到尾忍饰，即滿足題意。
ans++;
//為了驗證是否正確耐版，進行了下標打屿艄弧（下標0代表字符串的第一位）
System.out.println("match:" + i);
}
}
}
}
枚舉方法的時間復(fù)雜度計算：
?假設(shè)s1長度為m，s2長度為n粪牲，掃描s1需要O(m)古瓤，掃描s2需要O(n)，上述代碼最壞情況下是O(mn)腺阳。
對于字符串較短的時候落君，可以利用枚舉暴力實現(xiàn)，可是當字符串很長的時候亭引，則會超時绎速，因為計算機1s大概可以進行10 ^ 8次方規(guī)模的運算，當n和m超過10 ^ 4次方的時候焙蚓，就會超時纹冤，而競賽的數(shù)據(jù)往往是10 ^ 9甚至更大，這時需要更優(yōu)的算法解決购公，所以下面將介紹Rabin-Karp算法萌京，如何將O(nm)時間復(fù)雜度降到O(n + m)。
RabinKarp算法的思路：可以對s2字符串進行特定的處理宏浩，得出一個整數(shù)值知残，這個值在術(shù)語上稱為哈希值，只要能求出這個值绘闷，只需要對s1字符串的每個字符截取長度為s2的子字符串進行求哈希值橡庞，比對s1子字符串和s2 字符串的哈希值是否相等來判斷是否相等。
那么如何求出這個字符串的哈希值呢印蔗？
每個字符都有一個ASCII碼相對應(yīng)扒最，那么就可以利用進制的計算原理來求出哈希值：
?例如：
?我們可以把它看成是31進制，則abc可以表示為：
?31 ^ 2 * a + 31 ^ 1 * b + 31 ^ 0 * c
這樣子就可以把這個字符串的哈希值求出來了华嘹。但這樣用代碼實現(xiàn)比較難施展開吧趣，我們可以對這條式進行變換： (((0 * 31) + a ) * 31 + b) * 31 + c = 31 ^ 2 * a + 31 ^ 1 * b + 31 ^ 0 * c
這樣子就可以通過循環(huán)計算哈希值了，代碼如下：
//計算Hash值
private static long hash(String s) {
int len = s.length();
long hash = 0;
long send = 31;//設(shè)置種子數(shù)為31，代表是31進制計算;
/**
* 假設(shè)s長度為3
* 則s的hash值計算公式為：
* send^2 * s2[0] + send * s2[1] + send * s2[2]
* 等價于 = (((send * 0) + s2[0]) * send) + s2[1]) * send + s2[2]
*/
for(int i = 0; i < len; i++) {
hash = send * hash + s.charAt(i);
}
return hash;
}
那么在知道如何計算一個字符串的哈希值之后强挫，我們就可以通過比較2個字符串的哈希值來判斷是否相等了岔霸。
代碼如下：
//通過計算哈希值
private static void solve02(String s1, String s2) {
//1.先計算s2的hash值
long hash_s2 = hash(s2);
//2.通過遍歷求出每個字符作為初始位置且長度為s2的長度的字符串的hash值
int len_s2 = s2.length();
int len_s1 = s1.length();
for(int i = 0; i + len_s2 <= len_s1; i++) {
long hash_s1 = hash(s1.substring(i, i + len_s2));//計算s1中長度為s2的字串哈希值
if(hash_s1 == hash_s2) {
System.out.println("match:" + i);//i表示s1串的下標，下標從0開始
}
}
//3.比較兩個hash值是否相同
}
可是我們發(fā)現(xiàn)在上述的代碼中俯渤，時間復(fù)雜度依然是O(mn)呆细，為什么呢?
一開始需要求一次s2的哈希值，時間復(fù)雜度是O(n)
在s1字符串里每長度為n字符串都要求一次哈希值所以是O(nm)
所以最后還是O(mn)復(fù)雜度八匠。這相對于枚舉其實也沒有什么優(yōu)化呀絮爷！
其實接下來才是RabinKarp算法的精髓！!!!!!!!!!!
RabinKarp算法的精髓就是利用滾動哈希來算出解梨树，什么是滾動哈希坑夯，一開始我也是一臉懵，其實滾動哈希還是挺容易理解的抡四，相對于動態(tài)規(guī)劃柜蜈，哈哈！
我們不妨想一下指巡，比如淑履，給出一個字符串s1為abcd，s2為abc厌处，根據(jù)上述哈希值計算鳖谈，計算出了下標為0到下標為2的子串的哈希值，按照上述方法阔涉，接下來就是計算bcd的哈希值缆娃。滾動哈希的精髓就在此，我們已知abc的哈希值瑰排，要求的是bcd的哈希值贯要，那么abc和bcd這兩個字符串存在著公共字串，那就是bc椭住，那我們不就可以通過前一個字符串的哈希值乘上種子數(shù)（進制）減去 種子數(shù) ^ length(abc) + d 崇渗。
計算abc哈希值：31 ^ 2 * a + 31 ^ 1 * b + 31 ^ 0 * c
計算abcd哈希值：31 ^ 3 * a + 31 ^ 2 * b + 31 ^ 1 * c + 31 ^ 0 * d
可以得到 abc→abcd = (abc) * 31 + d
那么我們就能通過逆推得出bcd的哈希值
即 bcd = (abc ) * 31 + d - a * 31 ^ 3
代碼：
private static void solve03(String s1, String s2) {
// 1.先計算s2的hash值
long hash_s2 = hash(s2);
int len_s2 = s2.length();
int len_s1 = s1.length();
long[] hash_s1 = new long[len_s1 - len_s2 + 1];//s1所有的字串長度為s1的長度 - s2的長度 + 1
hash_s1[0] = hash(s1.substring(0, len_s2));//先算出s1中第一個長度為s2的字串的哈希值
int send = 31;
int ans = 0;
for (int i = len_s2; i < len_s1; i++) {//從已計算過哈希值的后一個字符開始
char newChar = s1.charAt(i);//記錄需要添加的新字符
char oldChar = s1.charAt(i - len_s2);//記錄需要刪除的舊字符
long v = (long) (hash_s1[i - len_s2] * send - oldChar * Math.pow(send, len_s2) + newChar) % Long.MAX_VALUE;//根據(jù)上述逆推公式
hash_s1[i - len_s2 + 1] = v; //賦值
}
for(int i = 0; i < hash_s1.length; i++) {
if (hash_s1[i] == hash_s2) { // 當兩個哈希值相同的時候，即滿足題意京郑。
ans++;
// 為了驗證是否正確宅广，進行了下標打印（下標0代表字符串的第一位）
System.out.println("match:" + i);
}
}
}
根據(jù)代碼我們可以計算出它的時間復(fù)雜度
計算s2的哈希值需要O(n);
計算s1的每個字串的哈希值需要O(m)些举，為什么不再是O(mn), 因為每個字串的哈希值是從上一個字串哈希值通過公式計算出來的值跟狱，不再需要遍歷字串的長度計算哈希值，所以每一次計算字串的時間復(fù)雜度為O(1);
最后掃描一次求出的s1字串哈希值需要O(m);
所以一共的時間復(fù)雜度為O(n + 2m),其中2m的2為常數(shù)項户魏，可以省略驶臊，最后的時間復(fù)雜度為O(n + m)!!!!!!
完整代碼：
public class Main {
public static void main(String[] args) {
String s1 = "abcaabcaabcbcabc";
String s2 = "abc";
solve01(s1, s2);
solve02(s1, s2);
solve03(s1, s2);
}
private static void solve03(String s1, String s2) {
System.out.println("--------------->滾動哈希：");
// 1.先計算s2的hash值
long hash_s2 = hash(s2);
int len_s2 = s2.length();
int len_s1 = s1.length();
long[] hash_s1 = new long[len_s1 - len_s2 + 1];//s1所有的字串長度為s1的長度 - s2的長度 + 1
hash_s1[0] = hash(s1.substring(0, len_s2));//先算出s1中第一個長度為s2的字串的哈希值
int send = 31;
int ans = 0;
for (int i = len_s2; i < len_s1; i++) {//從已計算過哈希值的后一個字符開始
char newChar = s1.charAt(i);
char oldChar = s1.charAt(i - len_s2);
long v = (long) (hash_s1[i - len_s2] * send - oldChar * Math.pow(send, len_s2) + newChar) % Long.MAX_VALUE;
hash_s1[i - len_s2 + 1] = v;
}
for(int i = 0; i < hash_s1.length; i++) {
if (hash_s1[i] == hash_s2) { // 當j == len_s2的時候則說明第二個循環(huán)從頭掃到尾挪挤，即滿足題意。
ans++;
// 為了驗證是否正確关翎，進行了下標打涌该拧（下標0代表字符串的第一位）
System.out.println("match:" + i);
}
}
}
private static void solve01(String s1, String s2) {
System.out.println("--------------->枚舉：");
int len_s1 = s1.length();
int len_s2 = s2.length();
int ans = 0;// 記錄答案
for (int i = 0; i < len_s1; i++) { // 掃描s1字符串
if (s1.charAt(i) == s2.charAt(0)) { // 當s2第一個字符與s1字符串的第一個字符匹配上的時候
int j = 0;
for (j = 1; j < len_s2; j++) { // 利用第二個指針控制兩個字符串的下標驗證是否滿足要求
if (s1.charAt(i + j) != s2.charAt(j)) { // 不滿足則退出循環(huán)
break;
}
}
if (j == len_s2) { // 當j == len_s2的時候則說明第二個循環(huán)從頭掃到尾，即滿足題意纵寝。
ans++;
// 為了驗證是否正確论寨，進行了下標打印（下標0代表字符串的第一位）
System.out.println("match:" + i);
}
}
}
}
private static void solve02(String s1, String s2) {
System.out.println("--------------->未優(yōu)化哈希計算：");
// 1.先計算s2的hash值
long hash_s2 = hash(s2);
// 2.通過遍歷求出每個字符作為初始位置且長度為s2的長度的字符串的hash值
int len_s2 = s2.length();
int len_s1 = s1.length();
for (int i = 0; i + len_s2 <= len_s1; i++) {
long hash_s1 = hash(s1.substring(i, i + len_s2));
if (hash_s1 == hash_s2) {
System.out.println("match:" + i);// i表示s1串的下標店雅，下標從0開始
}
}
// 3.比較兩個hash值是否相同
}
// 計算Hash值
private static long hash(String s) {
int len = s.length();
long hash = 0;
long send = 31;// 設(shè)置種子數(shù)為31;
/**
* 假設(shè)s長度為3 則s2的hash值計算公式為： send^2 * s2[0] + send * s2[1] + send * s2[2] 等價于 =
* (((send * 0) + s2[0]) * send) + s2[1]) * send + s2[2]
*/
for (int i = 0; i < len; i++) {
hash = send * hash + s.charAt(i);
}
return hash;
}
}
最后我相信你們會產(chǎn)生疑問政基，萬一不同的字符串算出來的哈希值一樣呢？
是的闹啦，會出現(xiàn)這種情況，但是根據(jù)大量數(shù)據(jù)得出結(jié)論：使用100000個不同字符串產(chǎn)生的沖突數(shù)辕坝，大概在0~3波動窍奋，使用100百萬不同的字符串，沖突數(shù)大概在110+范圍波動酱畅。所以琳袄，如果想要確保萬無一失，可以在判斷哈希值相等的時候再補一刀纺酸，就是判斷兩個串是否相同窖逗，但這樣會降低效率，不過在程序比賽中餐蔬，一般不會出現(xiàn)波動碎紊，可以省略！７怠仗考！
