最近刷題刷到leetcode的第28題，原題是這樣的：
這么看來這個貌似好簡單
1. 地面層
1.1 演算法實作
/*
*
* [28] 實作 strStr()
*/
public class Solution {
public int StrStr(string haystack, string needle) {
return haystack.IndexOf(needle);
}
}
1.2 演算法結果
想了想這樣不就可以了嗎？
對的，是的 這樣就可以了，但是我們如果能夠做到知其然且知其所以然是不是更可以呢？
2. 對流層(BF-暴力演算法與RK演算法)
2.1. BF演算法
BF演算法-Brute Force演算法，暴力匹配演算法也稱簡單匹配演算法，
2.1.1. BF演算法介紹
其基本思路是：
從目標串s=”s0 s1 … sn-1”的第一個字符開始和模式串t=”t0 t1 … tm-1”中的第一個字符比較，若相等，則繼續逐個比較后續字符，否則，從目標串s的第2個字符開始重新與模式串t的第一個字符進行比較，依次類推，若從目標串s的第i個字符開始，每個字符依次和模式串t中的對應字符相等，則匹配成功，該演算法回傳i;否則匹配失敗，回傳-1，
2.1.2. BF演算法實作
基于上圖和上面的基本思路我們可以撰寫如下代碼：
/*
*
* [28] 實作 strStr()
*/
public class Solution {
public int StrStr(string haystack, string needle) {
if(needle=="")
{
return 0;
}
for (int i = 0; i < haystack.Length; i++)
{
int j = 0;
for (; j < needle.Length; j++)
{
if( i + j < haystack.Length)
{
if(haystack[i+j]!=needle[j])
{
break;
}
}
else
{
return -1;
}
}
if(j==needle.Length)
{
return i;
}
}
return -1;
}
}
2.1.3. BF演算法缺陷
依據上述兩張圖片中的內容我們可以發現最差時間復雜度會在N*M,主要是由于暴力破解的程序中有非常多的無效比對,而如果我們能夠去除演算法中的無效比對引導演算法找一個正確的再次比對的起始點，那么無疑演算法效率將有一個顯著的提升，
2.1.4 演算法結果
2.2. RK演算法
RK演算法的全稱叫Rabin-Karp演算法，是由它的兩位發明者Rabin和Karp的名字來命名的，
2.2.1. RK演算法介紹
我在講BF演算法的時候講過，如果模式串?度為m，主串?度為n，那在主串中，就會有n-m+1個?度為m的?串，我們只需要
暴?地對?這n-m+1個?串與模式串，就可以找出主串與模式串匹配的?串，
2.2.2. RK演算法實作
/*
*
* [28] 實作 strStr()
*/
public class Solution {
public int StrStr(string haystack, string needle)
{
int n = haystack.Length, m = needle.Length;
if (needle == "")
{
return 0;
}
Dictionary<string,int> dictionary=new Dictionary<string, int>();
for (int i = 0; i < n; i++)
{
if(i+m>n)
{
break;
}
string strKey=haystack.Substring(i,m);
if(!dictionary.ContainsKey(strKey))
{
dictionary.Add(strKey,i);
}
}
return dictionary.ContainsKey(needle)?dictionary[needle]:-1;
}
}
2.2.3. 字典RK演算法結果
3. 平流層(KMP演算法)
KMP演算法是一種改進的字串匹配演算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人們稱它為克努特—莫里斯—普拉特操作（簡稱KMP演算法），KMP演算法的核心是利用匹配失敗后的資訊，盡量減少模式串與主串的匹配次數以達到快速匹配的目的，具體實作就是通過一個next()函式實作，函式本身包含了模式串的區域匹配資訊，KMP演算法的時間復雜度O(m+n)
從上述動圖中我們可以看到依據了某種特殊的方式過濾了無效比對,而在整個比對程序中，其實目標主串只是作為目標，作為獲取的結果，所以說白了KMP演算法是研究模式串的演算法，只需要研究當上一個起始節點比對失敗之后跳轉到第多少個節點進行比對的演算法
3.1. 演算法思路演算
- 所以在
標準演算法中經常使用next陣列來記錄，所以next陣列是記錄模式串的陣列資訊， - 當計算出
next陣列,從第一個字符開始比對， - 如果成功，則繼續比對下一個字符
- 如果失敗則計算失敗
下標的next陣列值，跳轉，繼續第三步
3.1.1. next陣列中值代表的實際意義
next陣列表達當前下標前組成的字串，其最長真子前綴字串和最長真子后綴字串相等的最長真子字串的長度
-
舉例說明：
- 字串：ACBAC
- 最長真子前綴字串：ACBA
- 最長真子后綴字串：CBAC
- 最長真子前綴字串=最長真子后綴字串=AC=AC
- 最長真子字串的長度：AC=2
3.2. 演算法代碼
/*
*
* [28] 實作 strStr()
*/
public class Solution {
public int StrStr(string haystack, string needle)
{
int n = haystack.Length, m = needle.Length;
if (needle == "")
{
return 0;
}
int[] next = new int[m];
InitNextArr(next, needle);
for (int i = 0, j = 0; i < n; i++)
{
while (j > 0 && haystack[i] != needle[j])
{
j = next[j - 1];
}
if (haystack[i] == needle[j])
{
j++;
}
if (j == m)
{
return i - m + 1;
}
}
return -1;
}
private void InitNextArr(int[] next, string needle)
{
for (int i = 1, j = 0; i < needle.Length; i++)
{
while (j > 0 && needle[i] != needle[j])
{
j = next[j - 1];
}
if (needle[i] == needle[j])
{
j++;
}
next[i] = j;
}
}
}
3.3. 演算法結果
4. 中間層(BM演算法)
具體參考如下：https://zhuanlan.zhihu.com/p/63596339
4.1. 演算法介紹
1977年，Robert S.Boyer和J Strother Moore提出了另一種在O(n)時間復雜度內，完成字串匹配的演算法，其在絕大多數場合的性能表現，比KMP演算法還要出色
BM演算法包含兩部分，分別是壞字符規則（bad character rule）和好后綴規則（good suffix shift）
其演算法是要：可以?次性把模式串往后多滑動?位，把模式串移動到c的后?，那么要將模式串向后滑動多少位呢?,就是使用上述的壞字符規則（bad character rule）和好后綴規則（good suffix shift）來確定的，從而保證后移位數的同時不會導致遺漏匹配
4.2. 演算法實作
/*
* @lc app=leetcode.cn id=28 lang=csharp
*
* [28] 實作 strStr()
*/
// @lc code=start
public class Solution {
public int StrStr(string haystack, string needle)
{
return BM(haystack.ToCharArray(), haystack.Length, needle.ToCharArray(), needle.Length);
}
private static int SIZE = 256; // 全域變數或成員變數
/// <summary>
/// 構建壞字符哈希表
/// </summary>
/// <param name="b"></param>
/// <param name="m"></param>
/// <param name="bc"></param>
private void GenerateBC(char[] b, int m, int[] bc)
{
for (int i = 0; i < SIZE; ++i)
{
bc[i] = -1; // 初始化bc
}
for (int i = 0; i < m; ++i)
{
int ascii = (int)b[i]; // 計算b[i]的ASCII值
bc[ascii] = i;
}
}
/// <summary>
/// 構建壞字符哈希表
/// b表示模式串，m表示?度，suffix，prefix陣列事先申請好了
/// </summary>
/// <param name="b"></param>
/// <param name="m"></param>
/// <param name="suffix"></param>
/// <param name="prefix"></param>
private void GenerateGS(char[] b, int m, int[] suffix, bool[] prefix)
{
for (int i = 0; i < m; ++i)
{
// 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i)
{
// b[0, i]
int j = i;
int k = 0; // 公共后綴?串?度
while (j >= 0 && b[j] == b[m - 1 - k])
{
// 與b[0, m-1]求公共后綴?串
--j;
++k;
suffix[k] = j + 1; //j+1表示公共后綴?串在b[0, i]中的起始下標
}
if (j == -1)
{
prefix[k] = true; //如果公共后綴?串也是模式串的前綴?串
}
}
}
/// <summary>
/// a,b表示主串和模式串；n，m表示主串和模式串的?度，
/// </summary>
/// <param name="a"></param>
/// <param name="n"></param>
/// <param name="b"></param>
/// <param name="m"></param>
/// <returns></returns>
public int BM(char[] a, int n, char[] b, int m)
{
int[] bc = new int[SIZE]; // 記錄模式串中每個字符最后出現的位置
GenerateBC(b, m, bc); // 構建壞字符哈希表
int[] suffix = new int[m];
bool[] prefix = new bool[m];
GenerateGS(b, m, suffix, prefix);
int i = 0; // j表示主串與模式串匹配的第?個字符
while (i <= n - m)
{
int j;
for (j = m - 1; j >= 0; --j)
{
// 模式串從后往前匹配
if (a[i + j] != b[j]) break; // 壞字符對應模式串中的下標是j
}
if (j < 0)
{
return i; // 匹配成功，回傳主串與模式串第?個匹配的字符的位置
}
int x = j - bc[(int)a[i + j]];
int y = 0;
if (j < m - 1)
{
// 如果有好后綴的話
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.Max(x, y);
}
return -1;
}
/// <summary>
/// j表示壞字符對應的模式串中的字符下標; m表示模式串?度
/// </summary>
/// <param name="j"></param>
/// <param name="m"></param>
/// <param name="suffix"></param>
/// <param name="prefix"></param>
/// <returns></returns>
private int moveByGS(int j, int m, int[] suffix, bool[] prefix)
{
int k = m - 1 - j; // 好后綴?度
if (suffix[k] != -1) return j - suffix[k] + 1;
for (int r = j + 2; r <= m - 1; ++r)
{
if (prefix[m - r] == true)
{
return r;
}
}
return m;
}
}
// @lc code=end
4.3. 演算法結果
5. 大氣層(見山還是山)
5.1. 對于系統函式而言
在作業中如非必要我們可以直接使用語言自帶的IndexOf函式來做
5.2. 對于BF演算法而言
-
第?，實際的軟體開發中，?部分情況下，模式串和主串的?度都不會太?，?且每次模式串與主串中的?串匹配的時候，當
中途遇到不能匹配的字符的時候，就可以就停?了，不需要把m個字符都?對?下，所以，盡管理論上的最壞情況時間復雜度
是O(n*m)，但是，統計意義上，?部分情況下，演算法執?效率要?這個?很多， -
第?，樸素字串匹配演算法思想簡單，代碼實作也?常簡單，簡單意味著不容易出錯，如果有bug也容易暴露和修復，在?程
中，在滿?性能要求的前提下，簡單是?選，這也是我們常說的KISS（Keep it Simple and Stupid）設計原則，
5.3 辯證的看待問題
一般來說在作業中如非必要我們可以直接使用語言自帶的IndexOf函式來做
- Java源代碼實作
/**
* Code shared by String and StringBuffer to do searches. The
* source is the character array being searched, and the target
* is the string being searched for.
*
* @param source the characters being searched.
* @param sourceOffset offset of the source string.
* @param sourceCount count of the source string.
* @param target the characters being searched for.
* @param targetOffset offset of the target string.
* @param targetCount count of the target string.
* @param fromIndex the index to begin searching from.
*/
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
- 構建測驗代碼
在Java中構建代碼，我們將Java原始碼拿出來，單獨運行，跳過Java代碼預熱，否則就是不講武德
具體代碼可見第6節
private static void initListArr(List<String> listTestInfo, List<String> listTestTarget) {
listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsadknsadkjsaifamdoaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsdkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpooaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaipoasdsamdoaksdpoaaifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaaaifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaipoasdsamdoaksdpoaaisamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab");
listTestTarget.add("dsadoi");
listTestTarget.add("sadkjsaifa");
listTestTarget.add("dpoasdas,d;lk");
listTestTarget.add("amdsakdpoasdsa;lk");
listTestTarget.add("aifamdsakdpooas,d;lk");
listTestTarget.add("dfamdakdpoasdsamdoaksdpo");
listTestTarget.add("dsifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestTarget.add("dsadoijsadknsadkjsaifam");
listTestTarget.add("aaaaaaaaaaaaaaaaab");
}
運行時間如下
Java自帶演算法時間：2688
-------------------------------------------------------------------
BM演算法時間：3601
-------------------------------------------------------------------
KMP演算法時間：2134
private static void initListArr(List<String> listTestInfo, List<String> listTestTarget) {
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsdkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpooaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaipoasdsamdoaksdpoaaifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaaaifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaipoasdsamdoaksdpoaaisamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab");
// listTestTarget.add("dsadoi");
// listTestTarget.add("sadkjsaifa");
// listTestTarget.add("dpoasdas,d;lk");
// listTestTarget.add("amdsakdpoasdsa;lk");
// listTestTarget.add("aifamdsakdpooas,d;lk");
// listTestTarget.add("dfamdakdpoasdsamdoaksdpo");
// listTestTarget.add("dsifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestTarget.add("dsadoijsadknsadkjsaifam");
listTestTarget.add("aaaaaaaaaaaaaaaaab");
}
Java自帶演算法時間：706
-------------------------------------------------------------------
BM演算法時間：422
-------------------------------------------------------------------
KMP演算法時間：260
如非必要就是用語言自帶的函式，如果在效率上有特殊的要求可以自己根據上述演算法思想優化
6. 附代碼
大氣層代碼
import org.apache.commons.lang3.time.StopWatch;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;
import java.util.concurrent.TimeUnit;
/**
* @Classname Main
* @Description 主表單函式
* @Date 2021/9/7 15:00
* @Created by xiaocai
*/
public class Main {
private static void initListArr(List<String> listTestInfo, List<String> listTestTarget) {
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsdkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpooaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaipoasdsamdoaksdpoaaifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaaaifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestInfo.add("dsadoijsadknsadkjsaifamdsakdpoaipoasdsamdoaksdpoaaisamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
listTestInfo.add("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab");
// listTestTarget.add("dsadoi");
// listTestTarget.add("sadkjsaifa");
// listTestTarget.add("dpoasdas,d;lk");
// listTestTarget.add("amdsakdpoasdsa;lk");
// listTestTarget.add("aifamdsakdpooas,d;lk");
// listTestTarget.add("dfamdakdpoasdsamdoaksdpo");
// listTestTarget.add("dsifamdakdpoasdsamdoaksdpoaasddkjsaifamdsakdpoasdsamdoaksdpoasdas,d;lk");
// listTestTarget.add("dsadoijsadknsadkjsaifam");
listTestTarget.add("aaaaaaaaaaaaaaaaab");
}
public static void main(String[] args) {
List<String> listTestInfo=new ArrayList<>();
List<String> listTestTarget=new ArrayList<>();
initListArr(listTestInfo,listTestTarget);
Main main=new Main();
//創建并啟動StopWatch
StopWatch stopwatch = StopWatch.createStarted();
for (int k = 0; k < 100000; k++) {
for (int i = 0; i <listTestInfo.size() ; i++) {
for (int j = 0; j <listTestTarget.size() ; j++) {
main.javaIndexOf(listTestInfo.get(i).toCharArray(),0,listTestInfo.get(i).length(),
listTestTarget.get(j).toCharArray(),0,listTestTarget.get(j).length(),0);
}
}
}
stopwatch.stop();
System.out.println("Java自帶演算法時間："+stopwatch.getTime(TimeUnit.MILLISECONDS));
System.out.println("-------------------------------------------------------------------");
stopwatch = StopWatch.createStarted();
for (int k = 0; k < 100000; k++) {
for (int i = 0; i <listTestInfo.size() ; i++) {
for (int j = 0; j <listTestTarget.size() ; j++) {
main.BM(listTestInfo.get(i).toCharArray(),listTestInfo.get(i).length(),listTestTarget.get(j).toCharArray(),listTestTarget.get(j).length());
}
}
}
stopwatch.stop();
System.out.println("BM演算法時間："+stopwatch.getTime(TimeUnit.MILLISECONDS));
System.out.println("-------------------------------------------------------------------");
stopwatch = StopWatch.createStarted();
for (int k = 0; k < 100000; k++) {
for (int i = 0; i <listTestInfo.size() ; i++) {
for (int j = 0; j <listTestTarget.size() ; j++) {
main.KMP(listTestInfo.get(i).toCharArray(),listTestTarget.get(j).toCharArray());
}
}
}
stopwatch.stop();
System.out.println("KMP演算法時間："+stopwatch.getTime(TimeUnit.MILLISECONDS));
}
/**
* Code shared by String and StringBuffer to do searches. The
* source is the character array being searched, and the target
* is the string being searched for.
*
* @param source the characters being searched.
* @param sourceOffset offset of the source string.
* @param sourceCount count of the source string.
* @param target the characters being searched for.
* @param targetOffset offset of the target string.
* @param targetCount count of the target string.
* @param fromIndex the index to begin searching from.
*/
int javaIndexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
private static int SIZE = 256; // 全域變數或成員變數
/// <summary>
/// 構建壞字符哈希表
/// </summary>
/// <param name="b"></param>
/// <param name="m"></param>
/// <param name="bc"></param>
private void GenerateBC(char[] b, int m, int[] bc)
{
for (int i = 0; i < SIZE; ++i)
{
bc[i] = -1; // 初始化bc
}
for (int i = 0; i < m; ++i)
{
int ascii = (int)b[i]; // 計算b[i]的ASCII值
bc[ascii] = i;
}
}
/// <summary>
/// 構建壞字符哈希表
/// b表示模式串，m表示?度，suffix，prefix陣列事先申請好了
/// </summary>
/// <param name="b"></param>
/// <param name="m"></param>
/// <param name="suffix"></param>
/// <param name="prefix"></param>
private void GenerateGS(char[] b, int m, int[] suffix, boolean[] prefix)
{
for (int i = 0; i < m; ++i)
{
// 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i)
{
// b[0, i]
int j = i;
int k = 0; // 公共后綴?串?度
while (j >= 0 && b[j] == b[m - 1 - k])
{
// 與b[0, m-1]求公共后綴?串
--j;
++k;
suffix[k] = j + 1; //j+1表示公共后綴?串在b[0, i]中的起始下標
}
if (j == -1)
{
prefix[k] = true; //如果公共后綴?串也是模式串的前綴?串
}
}
}
/// <summary>
/// a,b表示主串和模式串；n，m表示主串和模式串的?度，
/// </summary>
/// <param name="a"></param>
/// <param name="n"></param>
/// <param name="b"></param>
/// <param name="m"></param>
/// <returns></returns>
public int BM(char[] a, int n, char[] b, int m)
{
int[] bc = new int[SIZE]; // 記錄模式串中每個字符最后出現的位置
GenerateBC(b, m, bc); // 構建壞字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
GenerateGS(b, m, suffix, prefix);
int i = 0; // j表示主串與模式串匹配的第?個字符
while (i <= n - m)
{
int j;
for (j = m - 1; j >= 0; --j)
{
// 模式串從后往前匹配
if (a[i + j] != b[j]) break; // 壞字符對應模式串中的下標是j
}
if (j < 0)
{
return i; // 匹配成功，回傳主串與模式串第?個匹配的字符的位置
}
int x = j - bc[(int)a[i + j]];
int y = 0;
if (j < m - 1)
{
// 如果有好后綴的話
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
/// <summary>
/// j表示壞字符對應的模式串中的字符下標; m表示模式串?度
/// </summary>
/// <param name="j"></param>
/// <param name="m"></param>
/// <param name="suffix"></param>
/// <param name="prefix"></param>
/// <returns></returns>
private int moveByGS(int j, int m, int[] suffix, boolean[] prefix)
{
int k = m - 1 - j; // 好后綴?度
if (suffix[k] != -1) return j - suffix[k] + 1;
for (int r = j + 2; r <= m - 1; ++r)
{
if (prefix[m - r] == true)
{
return r;
}
}
return m;
}
public int KMP(char[] haystack, char[] needle)
{
int n = haystack.length, m = needle.length;
if (needle.length==0)
{
return 0;
}
int[] next = new int[m];
InitNextArr(next, needle);
for (int i = 0, j = 0; i < n; i++)
{
while (j > 0 && haystack[i]!= needle[j])
{
j = next[j - 1];
}
if (haystack[i] == needle[j])
{
j++;
}
if (j == m)
{
return i - m + 1;
}
}
return -1;
}
private void InitNextArr(int[] next, char[] needle)
{
for (int i = 1, j = 0; i < needle.length; i++)
{
while (j > 0 && needle[i] != needle[j])
{
j = next[j - 1];
}
if (needle[i] == needle[j])
{
j++;
}
next[i] = j;
}
}
}
7. 參考鏈接
https://zhuanlan.zhihu.com/p/63596339
https://www.zhihu.com/question/21923021/answer/1825831303
{
while (j > 0 && haystack[i]!= needle[j])
{
j = next[j - 1];
}
if (haystack[i] == needle[j])
{
j++;
}
if (j == m)
{
return i - m + 1;
}
}
return -1;
}
private void InitNextArr(int[] next, char[] needle)
{
for (int i = 1, j = 0; i < needle.length; i++)
{
while (j > 0 && needle[i] != needle[j])
{
j = next[j - 1];
}
if (needle[i] == needle[j])
{
j++;
}
next[i] = j;
}
}
}
# 7. 參考鏈接
https://zhuanlan.zhihu.com/p/63596339
https://www.zhihu.com/question/21923021/answer/1825831303
https://leetcode-cn.com/problems/implement-strstr/solution/shi-xian-strstr-by-leetcode-solution-ds6y/
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/298704.html
標籤：其他
上一篇：SSL證書的主要作用
下一篇：git面試題總結