資訊專欄INFORMATION COLUMN
摘要：字符串和中，存放必須為字符串長(zhǎng)度例在中要從下標(biāo)處開(kāi)始查找說(shuō)明標(biāo)準(zhǔn)算法中，為研究方便，中存放的為各自字符串長(zhǎng)度。則計(jì)算字符串的哈希值公式如下，如圖算法導(dǎo)論上提供的示例圖算法二算法許多算法可以完成這個(gè)任務(wù)，算法簡(jiǎn)稱是最常用的之一。
面試題: 判斷字符串是否在另一個(gè)字符串中存在？
面試時(shí)發(fā)現(xiàn)好多人回答不好, 所以就梳理了一下已知的方法, 此文較長(zhǎng), 需要耐心的看下去。從實(shí)現(xiàn)和算法原理兩方面解此問(wèn)題， 其中有用PHP原生方法實(shí)現(xiàn)也有一些業(yè)界大牛創(chuàng)造的算法。
實(shí)現(xiàn) 方法一: 語(yǔ)言特性-內(nèi)置函數(shù)| 函數(shù) | 描述 | 版本 |
|---|---|---|
| strpos | 查找字符串首次出現(xiàn)的位置 | PHP 4, PHP 5, PHP 7 |
| stripos | 查找字符串首次出現(xiàn)的位置（不區(qū)分大小寫） | PHP 5, PHP 7 |
| strrpos | 計(jì)算指定字符串在目標(biāo)字符串中最后一次出現(xiàn)的位置 | PHP 4, PHP 5, PHP 7 |
| strripos | 計(jì)算指定字符串在目標(biāo)字符串中最后一次出現(xiàn)的位置（不區(qū)分大小寫） | PHP 5, PHP 7 |
| mb_strpos | 查找字符串在另一個(gè)字符串中首次出現(xiàn)的位置 | PHP 4 >= 4.0.6, PHP 5, PHP 7 |
| strstr | 查找字符串的首次出現(xiàn) | PHP 4, PHP 5, PHP 7 |
| stristr | strstr() 函數(shù)的忽略大小寫版本 | PHP 4, PHP 5, PHP 7 |
| substr_count | 計(jì)算字串出現(xiàn)的次數(shù) | PHP 4, PHP 5, PHP 7 |
| 函數(shù) | 描述 | 版本 |
|---|---|---|
| preg_match | 執(zhí)行匹配正則表達(dá)式 | PHP 4, PHP 5, PHP 7 |
| preg_match_all | 執(zhí)行一個(gè)全局正則表達(dá)式匹配 | PHP 4, PHP 5, PHP 7 |
= 2 ? true : false; } // strtok 可以么? // 在分割字符串時(shí)，split()與explode()誰(shuí)快?
| 函數(shù) | 描述 | 版本 |
|---|---|---|
| strtok | 標(biāo)記分割字符串 | PHP 4, PHP 5, PHP 7 |
| explode | 使用一個(gè)字符串分割另一個(gè)字符串 | PHP 4, PHP 5, PHP 7 |
| split | 用正則表達(dá)式將字符串分割到數(shù)組中 | PHP 4, PHP 5 |
| mb_split | 使用正則表達(dá)式分割多字節(jié)字符串 | PHP 4 >= 4.2.0, PHP 5, PHP 7 |
| preg_split | 通過(guò)一個(gè)正則表達(dá)式分隔字符串 | PHP 4, PHP 5, PHP 7 |
$aLen) {
return -1;
}
$data = [];
$aLastIndex = -1;
$bStartIndex = 0;
for($ai = 0; $ai < $aLen; $ai++) {
$av = $aArr[$ai];
$exists = false;
for($bi = $bStartIndex; $bi < $bLen; $bi++) {
$bv = $bArr[$bi];
if(($aLastIndex == -1 || $ai == ($aLastIndex + 1)) && $av == $bv) {
$exists = true;
break;
}
if ($aLastIndex != -1 && $ai == ($aLastIndex + 1) && $av != $bv) {
break;
}
}
if ($exists) {
$aLastIndex = $ai;
$bStartIndex = $bi + 1;
array_push($data, [
"value" => $av,
"index" => $ai
]);
} else {
$aLastIndex = -1;
$bStartIndex = 0;
$data = [];
}
if ($exists && $bLen == $bStartIndex) {
break;
}
}
if(!empty($data) && count($data) == $bLen) {
$begin = array_shift($data);
return $begin["index"];
} else {
return -1;
}
}
方法五: 樸素算法(暴力查找)
方法六: 字符串查找算法-Rabin-Karp算法#include#include using namespace std; #define BASE 256 #define MODULUS 101 void RabinKarp(char t[], char p[]) { int t_len = strlen(t); int p_len = strlen(p); // 哈希滾動(dòng)之用 int h = 1; for (int i = 0; i < p_len - 1; i++) h = (h * BASE) % MODULUS; int t_hash = 0; int p_hash = 0; for (int i = 0; i < p_len; i++) { t_hash = (BASE * t_hash + t[i]) % MODULUS; p_hash = (BASE * p_hash + p[i]) % MODULUS; } int i = 0; while (i <= t_len - p_len) { // 考慮到哈希碰撞的可能性，還需要用 memcmp 再比對(duì)一下 if (t_hash == p_hash && memcmp(p, t + i, p_len) == 0) cout << p << " is found at index " << i << endl; // 哈希滾動(dòng) t_hash = (BASE * (t_hash - t[i] * h) + t[i + p_len]) % MODULUS; // 防止出現(xiàn)負(fù)數(shù) if (t_hash < 0) t_hash = t_hash + MODULUS; i++; } } int main() { char t[100] = "It is a test, but not just a test"; char p[10] = "test"; RabinKarp(t, p); return 0; } 1, "e" => 2, "l" => 3, "o" => 4, "w" => 5, "r" => 6, "d" => 7, ); for ($i = 0; $i < $len; $i++) { $hash .= $hash_table[$str{$i}]; } return (int)$hash; } function rabin_karp($text, $pattern) { $n = strlen($text); $m = strlen($pattern); $text_hash = hash_string(substr($text, 0, $m), $m); $pattern_hash = hash_string($pattern, $m); for ($i = 0; $i < $n-$m+1; $i++) { if ($text_hash == $pattern_hash) { return $i; } $text_hash = hash_string(substr($text, $i, $m), $m); } return -1; } // 2 echo rabin_karp("hello world", "ello");方法七: 字符串查找算法-KMPpublic class KMP { public static int KMPSearch(String txt, String pat, int[] next) { int M = txt.length(); int N = pat.length(); int i = 0; int j = 0; while (i < M && j < N) { if (j == -1 || txt.charAt(i) == pat.charAt(j)) { i++; j++; } else { j = next[j]; } } if (j == N) return i - j; else return -1; } public static void getNext(String pat, int[] next) { int N = pat.length(); next[0] = -1; int k = -1; int j = 0; while (j < N - 1) { if (k == -1 || pat.charAt(j) == pat.charAt(k)) { ++k; ++j; next[j] = k; } else k = next[k]; } } public static void main(String[] args) { String txt = "BBC ABCDAB CDABABCDABCDABDE"; String pat = "ABCDABD"; int[] next = new int[pat.length()]; getNext(pat, next); System.out.println(KMPSearch(txt, pat, next)); } }方法八: 字符串查找算法-Boyer-Moorepublic class BoyerMoore { public static void getRight(String pat, int[] right) { for (int i = 0; i < 256; i++){ right[i] = -1; } for (int i = 0; i < pat.length(); i++) { right[pat.charAt(i)] = i; } } public static int BoyerMooreSearch(String txt, String pat, int[] right) { int M = txt.length(); int N = pat.length(); int skip; for (int i = 0; i <= M - N; i += skip) { skip = 0; for (int j = N - 1; j >= 0; j--) { if (pat.charAt(j) != txt.charAt(i + j)) { skip = j - right[txt.charAt(i + j)]; if (skip < 1){ skip = 1; } break; } } if (skip == 0) return i; } return -1; } public static void main(String[] args) { String txt = "BBC ABCDAB AACDABABCDABCDABDE"; String pat = "ABCDABD"; int[] right = new int[256]; getRight(pat,right); System.out.println(BoyerMooreSearch(txt, pat, right)); } }方法九: 字符串查找算法-Sundaypublic class Sunday { public static int getIndex(String pat, Character c) { for (int i = pat.length() - 1; i >= 0; i--) { if (pat.charAt(i) == c) return i; } return -1; } public static int SundaySearch(String txt, String pat) { int M = txt.length(); int N = pat.length(); int i, j; int skip = -1; for (i = 0; i <= M - N; i += skip) { for (j = 0; j < N; j++) { if (txt.charAt(i + j) != pat.charAt(j)){ if (i == M - N) break; skip = N - getIndex(pat, txt.charAt(i + N)); break; } } if (j == N) return i; } return -1; } public static void main(String[] args) { String txt = "BBC ABCDAB AACDABABCDABCDABD"; String pat = "ABCDABD"; System.out.println(SundaySearch(txt, pat)); } }方法十: 字符串查找算法-BF算法(Brute Force)#include#include #include int index_bf(char *s,char *t,int pos); int index_bf_self(char *s,char *t,int index); int main() { char s[]="6he3wor"; //標(biāo)準(zhǔn)BF算法中，s[0]和t[0]存放的為字符串長(zhǎng)度。 char t[]="3wor"; int m=index_bf(s,t,2); //標(biāo)準(zhǔn)BF算法 printf("index_bf:%d ",m); m=index_bf_self(s,t,2); //修改版BF算法，s和t中，不必再存放字符串長(zhǎng)度。 printf("index_bf_self:%d ",m); exit(0); } /* 字符串S和T中，s[0],t[0]存放必須為字符串長(zhǎng)度 例：s[]="7hi baby!" T[]="4baby" index_bf(s,t,1); pos：在S中要從下標(biāo)pos處開(kāi)始查找T (說(shuō)明：標(biāo)準(zhǔn)BF算法中，為研究方便，s[0],t[0]中存放的為各自字符串長(zhǎng)度。) */ int index_bf(char *s,char *t,int pos) { int i,j; if(pos>=1 && pos <=s[0]-"0") { i=pos; j=1; while(i<=s[0]-"0"&&j<=t[0]-"0") { if(s[i]==t[j]) { i++; j++; } else { j=1; i=i-j+2; } if(j>t[0]-"0") { return i-t[0]+"0"; } } return -1; } else { return -1; } } /* 修改版，字符串s和t中，不必再包含字符串長(zhǎng)度。 例：s[]="hi baby" t[]="baby" index_bf_self(s,t,0); index:在s中，從幾號(hào)下標(biāo)開(kāi)始查找 */ int index_bf_self(char *s,char *t,int index) { int i=index,j=0; while(s[i]!="