串的模式匹配
1.樸素的模式匹配(Brute-Force)算法
假設(shè)待匹配的目標(biāo)串是adbcade,而模式串是ade究抓,那么匹配的時候是按:
a--d--b-->不匹配;
d-->不匹配; //注意這里在上一個發(fā)現(xiàn)不匹配時弛随,是從上一個匹配開始的下一個位置開始重新匹配的。
Brute-Force算法的實現(xiàn):
public int indexOf(String target,String pattern){
//判斷目標(biāo)串,匹配串是否滿足條件巍沙。
if(pattern != null && target != null && target.length() >= pattern.length()){
//start指開始匹配的字符起始位置
int start = 0;
//count指匹配到的字符數(shù)目
int count = 0;
//當(dāng)目標(biāo)串剩余未匹配的長度大于或等于匹配串串長度犯祠,循環(huán)繼續(xù)
while(target.length() - start >= pattern.length()){
//滿足條件
if(target.charAt(count + start) == pattern.charAt(count)){
//匹配一個字符后加一。
count ++;
}else{
//不滿足匹配窖铡,count置零疗锐,起始匹配位置加一。
count = 0;
start ++;
}
//若count==pattern费彼,說明已經(jīng)完成了一次匹配滑臊。
if(count == pattern.length()){
return start;
}
}
}
//匹配失敗返回-1
return -1;
}
測試程序以及運行結(jié)果:
public static void main(String[] args) {
// TODO Auto-generated method stub
String target = "adbcade";
String pattern = "ade";
BruteForceStringPattern sfsp = new BruteForceStringPattern();
System.out.println(sfsp.indexOf(target, pattern));
}
4
Brute-Force算法易于理解,但是時間效率不高箍铲。它是一種帶回溯的模式匹配算法雇卷,將目標(biāo)串中所有長度為匹配串長度的字串依次與匹配串比較。
雖然沒有任何丟失可能匹配字符的可能,但是每次的匹配沒有用到前一次匹配的比較結(jié)果关划,比較多次重復(fù)膘融,降低了算法效率。
時間復(fù)雜度:
m = pattern.length();
n = target.length();
最好的情況:O(m) (一次比較成功)
最壞的情況:O(n(n-m+1)m) 一般n>>m祭玉,所以O(shè)(nm) (比較到最后一次才成功)
2.無回溯的模式匹配(KMP)算法
先來一波kmp算法的百科介紹:
KMP算法是一種改進的字符串匹配算法氧映,由D.E.Knuth,J.H.Morris和V.R.Pratt同時發(fā)現(xiàn)
脱货,因此人們稱它為克努特——莫里斯——普拉特操作(簡稱KMP算法)岛都。
KMP算法的關(guān)鍵是利用匹配失敗后的信息,盡量減少模式串與主串的匹配次數(shù)以達到快速匹配的目的振峻。
具體實現(xiàn)就是實現(xiàn)一個next()函數(shù)臼疫,函數(shù)本身包含了模式串的局部匹配信息。
無回溯的模式匹配算法首先目標(biāo)串的祛除了目標(biāo)串的回溯扣孟,其次烫堤,通過getNext()算法,匹配串也做到了部分不回溯凤价。
無回溯算法的核心是如何實現(xiàn)這個next()算法:
public int[] next(String pattern){
int i = -1;
int j = 0;
int[] next = new int[pattern.length()];
next[0] = -1;
while(j < pattern.length() - 1){
if(i == -1 || pattern.charAt(i) == pattern.charAt(j)){
i++;
j++;
next[j] = i;
}else{
i = -1;
}
}
return next;
}
實際上next()算法就是來 判斷pattern的子字符串與當(dāng)pattern的0位置開始的字符串是否相同鸽斟,第一個next[0]默認(rèn)為1,接下來的如果不相同next[i]為0利诺,如果第一個相同富蓄,為0,若連續(xù)開始相同,則依次++1
如:
aaaaaaa的next():
[-1,0,1,2,3,4,5]
abab的next():
[-1,0,0,1]
如果pattern的首字符在pattern剩余的字符串里沒有再出現(xiàn)過慢逾,那么getNext()獲取的next[]必然是[-1,0,...,0]這樣的立倍。
匹配方法如下:
public int kmp(String target,String pattern){
if(target != null && pattern != null && target.length() > pattern.length()){
int start = 0;
int[] next = next(pattern);
int count = next[start];
while(target.length() - start + count >= pattern.length()){
if(count == -1 || target.charAt(start) == pattern.charAt(count)){
count ++;
start ++;
}else{
//這里就是核心了,如果next[count] <= 0 目標(biāo)字符串直接從當(dāng)前的下一個開始比較侣滩。
//因為等于-1的話說明是在匹配第一個字符串口注,當(dāng)前匹配失敗,不可能再與pattern第一個字符匹配了君珠,當(dāng)然是要繼續(xù)匹配下一個寝志,如果是0的話,說明是在匹配第一個與pattern頭相同的串或者匹配與pattern頭無關(guān)的字符葛躏,匹配失敗澈段,當(dāng)然也是繼續(xù)匹配下一個字符串。
count = next[count];
}
if(count == pattern.length()){
return start - count;
}
}
}
return -1;
}
kmp算法的最壞的比較次數(shù)是m+n舰攒,next算法的時間復(fù)雜度是0(m),kmp比較是O(n),與BF算法相比悔醋,已經(jīng)大大縮小了比較的時間摩窃。