串的模式匹配操作
在字符串匹配问题中,我们期待察看S串中是否含有串T(模式串)。其中串S被称为主串,串T被称为子串。
如果在主串中查找到子串,则称为模式匹配成功,返回模式串的第一个字符在主串中出现的位置。
如果在主串中未找到子串,则称为模式匹配失败,返回-1。
Brute-Force与KMP算法是两种最经典的模式匹配算法。
Brute-Force算法
也称简单匹配算法,其基本思路是:从目标串s=”s0s1…sn-1”的第一个字符开始和模式串t=”t0t1…tm-1”中的第一个字符比较,若相等,则继续逐个比较后续字符,否则,从目标串s的第2个字符开始重新与模式串t的第一个字符进行比较,依次类推,若从目标串s的第i个字符开始,每个字符依次和模式串t中的对应字符相等,则匹配成功,该算法返回i;否则匹配失败,返回-1。
设主串s=“cddcdc”,模式串t=“cdc”,模式匹配过程如图:
public static int bruteforce(String source, String sub) {
int j = 0, i = 0,index=-1;
while (i < source.length() && j < sub.length()) {
if (source.charAt(i) == sub.charAt(j))
{
i++; j++;
} else {
// 使i回退到下一个字符,应为子串的前面j向可能匹配成功,而第j+1项失败,所以 i=i-j+1
i = i - j + 1;
j = 0;
}
}
if (j == sub.length()) {
index = i - sub.length();
} else {
index = -1;
}
return index;
}
Brute-Force算法总结:
该方法的优点是:算法简单明朗,便于实现记忆。
缺点是:进行了回溯,效率不高,而这些都是没有必要的。比如下图:
KMP算法
Brute-Force被称为简单模式匹配算法。KMP算法是它的改进算法。
一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此称之为KMP算法。此算法可以在O(n+m)的时间数量级上完成串的模式匹配操作,其基本思想是:每当匹配过程中出现字符串比较不等时,不需回溯指针,而是利用已经得到的“部分匹配”结果将模式向右“滑动”尽可能远的一段距离,继续进行比较。
模式串求最大真子串
例如:求aaaab next[j]。
计算模式串的next[j]
当Si≠Tj,若模式串存在最大真子串,可将模式串T按照k=next[j]的值向右滑动,然后比较Si和Tk,若仍有Si≠Tk,则模式串T按照新的k=next[j]的值向右滑动后比较。这样的过程一直进行到k=next[k]=0,此时若Si≠T0,则模式串T不再向右滑动,随后比较Si+1和T0。
例如:主串为"aaaaaaab",子串为"aaaab",求采用KMP的模式匹配过程。
//KMP算法 public class KMP { //根据给定的模式串,求next[j]的算法 public static int[] getNext(String sub) { int j=1,k=0; int[] next = new int[sub.length()]; next[0]=-1; next[1]=0; while(j<sub.length()-1) { if(sub.charAt(j)==sub.charAt(k)) { next[j+1]=k+1; j++; k++; } else if(k==0) { next[j+1]=0; j++; } else { k=next[k]; } } return next; } //根据给定主串和子串,采用KMP算法 public static int kmp(String src,String sub) { //先生成模式串sub的next[j] int[] next = getNext(sub); //i:主串的游标 //j:子串的游标 int i=0,j=0,index=-1; while(i<src.length()&&j<sub.length()) { if(src.charAt(i)==sub.charAt(j)) { i++; j++; } else if(j==0) { i++; } else { j=next[j]; //向右滑动 } } if(j==sub.length()) { index = i-sub.length(); } return index; } }
- 博文推荐
- 学习进度之一:Stanford:Algo...
- 在C语言中,有两个获取当前时间的函数:l...
- 在C语言中,有两个获取当前时间的函数:l...
- 在C语言中,有两个获取当前时间的函数:l...
- 在C语言中,有两个获取当前时间的函数:l...
- 在C语言中,有两个获取当前时间的函数:l...
- 在C语言中,有两个获取当前时间的函数:l...
- 在C语言中,有两个获取当前时间的函数:l...
核心技术类目
全部主题
Java
VPN
Android
iOS
ERP
IE10
Eclipse
CRM
JavaScript
Ubuntu
NFC
WAP
jQuery
数据库
BI
HTML5
Spring
Apache
Hadoop
.NET
API
HTML
SDK
IIS
Fedora
XML
LBS
Unity
Splashtop
UML
components
Windows Mobile
Rails
QEMU
KDE
Cassandra
CloudStack
FTC
coremail
OPhone
CouchBase
云计算
iOS6
Rackspace
Web App
SpringSide
Maemo
Compuware
大数据
aptech
Perl
Tornado
Ruby
Hibernate
ThinkPHP
Spark
HBase
Pure
Solr
Angular
Cloud Foundry
Redis
Scala
Django
Bootstrap
Java
VPN
Android
iOS
ERP
IE10
Eclipse
CRM
JavaScript
Ubuntu
NFC
WAP
jQuery
数据库
BI
HTML5
Spring
Apache
Hadoop
.NET
API
HTML
SDK
IIS
Fedora
XML
LBS
Unity
Splashtop
UML
components
Windows Mobile
Rails
QEMU
KDE
Cassandra
CloudStack
FTC
coremail
OPhone
CouchBase
云计算
iOS6
Rackspace
Web App
SpringSide
Maemo
Compuware
大数据
aptech
Perl
Tornado
Ruby
Hibernate
ThinkPHP
Spark
HBase
Pure
Solr
Angular
Cloud Foundry
Redis
Scala
Django
Bootstrap