文章目錄

• 一、字符串查找
• 二、蠻力算法代碼示例

一、字符串查找

---

算法題目鏈接 : https://www.lintcode.com/problem/13/

在 一個字符串 中查找 另外一個字符串 第一次出現(xiàn)的位置 ;

如 : 在 “abcdefghijk” 中查找 “def” 第一次出現(xiàn)的位置 , 是 $4$ ;

該方法使用 暴力算法 , 兩層 for 循環(huán) , 肯定可以解決 ; 如果用暴力算法 , 那面試基本就涼了 ; 暴力算法的復(fù)雜度是 $O(m\times n)$ , $m$ 是第一個大字符串的長度 , $n$ 是被查找的字符串長度 ;

KMP 算法 是專門用于解決該問題的算法 , 該算法 只能用于解決在一個字符串中查找另外一個字符串的問題 ; KMP 算法主要靠背誦 , 沒有涉及到算法的理論 , 只能用于解決單一字符串查找問題 , 一般面試時不考慮使用該算法 ; KMP 算法的算法復(fù)雜度是 $O(m+n)$ ;

Rabin-Karp 算法 比 KMP 算法更簡單 , 其基本原理就是比較字符串的 哈希碼 ( HashCode ) , 快速的確定子字符串是否等于被查找的字符串 ;

二、蠻力算法代碼示例

---

蠻力算法 :

需要進(jìn)行雙層循環(huán)遍歷 ;

外層循環(huán) 遍歷 source 字符串 , 遍歷 source.length() - target.length() 次 ,
假設(shè)被遍歷的索引 i 開始 , target.length() 位字符串 與 target 字符串是否相等 ,
如果相等 , 則該索引就是題目中想要的結(jié)果 ,
如果不相等 , 那么繼續(xù)遍歷下一個索引 ;

內(nèi)層循環(huán) 就是遍歷 target 字符串 , 逐位對比 兩個字符串是否相等 ;

代碼 :

class Solution {/*** 蠻力算法 : 雙層循環(huán), 外層循環(huán)循環(huán) source, 內(nèi)層循環(huán)循環(huán) target 對應(yīng)字符是否相等* @param source:在該字符串中查找子字符串* @param target:被查找的字符串* @return: return the index*/public int strStr(String source, String target) {if (target == null || "".equals(target)) {return 0;}for (int i = 0; i < source.length() - target.length() + 1; i++) {boolean notEqual = false;for (int j = 0; j < target.length(); j++) {if (source.charAt(i + j) != target.charAt(j)) {// 只要有一個字符不相等, 就說明遍歷的該子字符串不匹配notEqual = true;break;}}// 如果所有的字符都匹配, 即對比中沒有不相等的字符, 該 i 索引就是結(jié)果if (!notEqual) {return i;}}return -1;} }class Main {public static void main(String[] args) {int index = new Solution().strStr("mabcban", "cb");System.out.println(index);} }

總結(jié)

以上是生活随笔為你收集整理的【字符串】字符串查找 ( 蛮力算法 )的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。