文章目录
-
- BF算法
- Sunday匹配算法
- KMP算法
- BM算法
BF算法
暴力破解(就是BF算法),
算法核心思想:首先S[1]和T[1]比较，若相等，则再比较S[2]和T[2]，一直到T[M]为止；若S[1]和T[1]不等，则T向 右移动一个字符的位置，再依次进行比较。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，则匹配成功；否则失败。该算法最坏情况下要进行 M*(N-M+1)次比较，时间复杂度为O(M*N)
比如: String a =“123456789” String b= “23”
其实就是循环 a一个一个字符匹配，开始a[0]和b[0]匹配，没有找到，直接不用找b[1]，直接用a[1]和b[0]匹配发现已经 找到，然后继续用
a[2]和b[1]匹配发现已经 找到。前且是b字符串末尾。说明已经完全找到。返回结果
代码实现:
public class 暴力解法 {
public static void main(String args[]){
String str1 = "ailkmno";
String str2 = "ilkm";
int n = find(str1,str2);
System.out.println(str2+"在"+str1+"中出现的位置是："+n);
}
public static int find(String str1,String str2){
char[] c1=str1.toCharArray();
char[] c2=str2.toCharArray();
int j=0;
int i=0;
for(;i<str1.length();){
if(j>=str2.length()-1){
break;
}
if(c1[i]==c2[j] ){
i=i+1;
j=j+1;
}else{
i=i+1;
}
}
System.out.println(i+" "+j);
return i-str2.length()+1;
}
}
Sunday匹配算法
Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。
Sunday算法其实思想跟BM算法很相似，只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在匹配串中出现则直接跳过，即移动步长= 匹配串长度+ 1；否则，同BM算法一样其移动步长=匹配串中最右端的该字符到末尾的距离+1。
举例:
假设我们有如下字符串：
S = “LESSONS TEARNED IN SOFTWARE TE”;
T = “SOFTWARE”;
(5) k指向的模式串T字符与m指向的主串S字符“E”相等，因此再次移动模式串1位。
代码实现如下:
import java.util.Arrays;
public class Sunday算法 {
//创建下一序号表,即记录字母对应下标
public static int[] next(char[] T) {
//初始化序号数组
int []next=new int[65536];
//填充坏字符序号
Arrays.fill(next, -1);
//填充好字符序号
for(int j=0;j<T.length;j++) {
next[T[j]]=j;
}
return next;
}
/**
* sunday查找
* @param S 正文字符数组
* @param T 模式字符数组
* @return 匹配位置
*/
public static int sunday(char[] S,char[] T) {
//检查输入参数有效
if (S==null||T==null||S.length==0 || T.length==0 ||T.length>S.length){
return -1;
}
//获取下一序号数组
int next[]=next(T);
//遍历正文数组
int delta =S.length-T.length;
for (int i = 0; i <delta;) {
//从头开始比较
int j=0;
for (;j<T.length&&i+j<S.length; j++) {
if (T[j]!=S[i+j]) {
break;
}
}
//已经完全匹配
if (j==T.length) {
return i;
}
//后移长度不够
if (i+T.length>=S.length) {
return -1;
}
//后移偏移距离(根据末位下一字符在模式字符串中的位置判断偏移距离)
i+=T.length-next[S[i+T.length]];
}
//返回查找失败
return -1;
}
public static void main(String[] args) {
String text="LESSONS TEARNED IN SOFTWARE TE";
String pattern="SOFTWARE";
System.out.println("S:\t"+text);
System.out.println("T:\t"+pattern);
//测试下一序号数组
int next[]=next(pattern.toCharArray());
System.out.println("下一序号数组:");
for(int i=0;i<next.length;i++) {
if (next[i]!=-1) {
System.out.println("next['"+(char)i+"']:"+next[i]);
}
}
//测试Sunday查找算法
System.out.println("Sunday:\t"+sunday(text.toCharArray(),pattern.toCharArray()));
//Java内置的匹配方法,找出第一次匹配的index索引
System.out.println("String:\t"+text.indexOf(pattern));
}
}
KMP算法
KMP是一个解决模式串在文本串是否出现过以及若出现找出最早出现位置的算法.
KMP要做的就是通过一个next数组保存模式串中前后最长公共子序列的长度以保证每次回溯时通过next数组找到应回溯的位置节省大量无用的回溯比较.
next数组的计算方法:
模式串
ababa
子串
a 前缀:无 后缀:无 最长公共子序列长度:0
ab 前缀:a 后缀:b 最长公共子序列长度: 0
aba 前缀:a ab 后缀:a ba 最长公共子序列长度: 1
abab 前缀:a ab aba 后缀:b ab bab 最长公共子序列长度:2
ababa 前缀:a ab aba abab 后缀:a ba aba baba 最长公共子序列长度:3
next数组 0 0 1 2 3
KMP算法时间复杂度O(m+n)
算法实现:
public class KMP算法 {
//求出next数组
public static int[] kmpnext(String dest) {
int[] next=new int[dest.length()];
next[0]=0;
//i为子序列长度
for (int i = 1,j=0; i < dest.length(); i++) {
//循环内的i为后缀下标,j为前缀下标,同时j记录着当前最大公共子序列长度
while(j>0&&dest.charAt(j)!=dest.charAt(i)) {
j=next[j-1];
}
if (dest.charAt(i)==dest.charAt(j)) {
j++;
}
next[i]=j;
}
return next;
}
//KMP实现
public static int kmp(String str, String dest,int[] next){//str文本串 dest 模式串
for(int i = 0, j = 0; i < str.length(); i++){
while(j > 0 && str.charAt(i) != dest.charAt(j)){
j = next[j - 1];
}
if(str.charAt(i) == dest.charAt(j)){
j++;
}
if(j == dest.length()){
return i-j+1;
}
}
return 0;
}
public static void main(String[] args){
String a = "ababa";
String b = "ssdfgasdbababa";
int[] next = kmpnext(a);
int res = kmp(b, a,next);
System.out.println(res);
for(int i = 0; i < next.length; i++){
System.out.println(next[i]);
}
System.out.println(next.length);
}
}
BM算法
Boyer-Moore算法，简称BM算法。该算法从模式串的尾部开始匹配，且拥有在最坏情况下O(N)的时间复杂度。在实践中，比KMP算法的实际效能高。
例如,给定文本串"HERE IS A SIMPLE EXAMPLE"和模式串"EXAMPLE",现要查找模式串是否在文本串中,如果存在,返回模式串在文本串中的位置.
- 首先，"文本串"与"模式串"头部对齐，从尾部开始比较。"S"与"E"不匹配。这时，“S"就被称为"坏字符”（bad character），即不匹配的字符，它对应着模式串的第6位。且"S"不包含在模式串"EXAMPLE"之中（相当于最右出现位置是-1），这意味着可以把模式串后移6-(-1)=7位，从而直接移到"S"的后一位。
字符串搜索算法与匹配算法的总结 - 依然从尾部开始比较，发现"P"与"E"不匹配，所以"P"是"坏字符"。但是，"P"包含在模式串"EXAMPLE"之中。因为“P”这个“坏字符”对应着模式串的第6位（从0开始编号），且在模式串中的最右出现位置为4，所以，将模式串后移6-4=2位，两个"P"对齐。
字符串搜索算法与匹配算法的总结 - 依次比较，得到 “MPLE”匹配，称为"好后缀"（good suffix），即所有尾部匹配的字符串。注意，“MPLE”、“PLE”、“LE”、"E"都是好后缀。
字符串搜索算法与匹配算法的总结 - 发现“I”与“A”不匹配：“I”是坏字符。如果是根据坏字符规则，此时模式串应该后移2-(-1)=3位。
字符串搜索算法与匹配算法的总结 - 继续从尾部开始比较，“X”与“E”不匹配，因此“X”是“好字符”，根据“好字符规则”，后移 6 - 1 = 5位。这是，“X”与“X”对齐。
字符串搜索算法与匹配算法的总结 - 依次从尾部开始比较,所有字符都能匹配,查找成功. 坏字符算法:
字符串搜索算法与匹配算法的总结 坏字符算法实现: 字符串搜索算法与匹配算法的总结
/**
* 坏字符忽略映射
* @param T 模式字符数组
* @return 坏字符忽略映射
*/
public static int[] bmBc(char[] T) {
//初始忽略数组
/*
* 为了方便起见,就直接把UTF8编码用65536个字符全表示了,
* 这样就不会漏掉哪个字符了
*/
int []bmBc = new int[65536];
//填充坏字符序号
Arrays.fill(bmBc, -1);
//填充好字符序号(以最后位置为准)
int m=T.length;
/*
* for循环bmBc[x[i]]中x[i]表示模式串中的第i个字符
* 为什么循环中,i从小到大的顺序计算呢?技巧就在这儿了
* 在同一个字符多次出现的时候以最靠右的那个字符到尾部的距离为最终距离.
* 当然,如果是没在模式串中出现的字符,距离就是m
*/
for(int i=0;i<m;i++) {
bmBc[T[i]]=m-1-i;
}
//返回忽略数组
return bmBc;
}
好后缀算法:
(2) 模式串中没有子串匹配上后缀,此时需要寻找模式串的一个最长前缀,并让该前缀等于 好后缀 的后缀 ,寻找到该前缀后,让该前缀和好后缀对齐即可.
为了实现 好后缀 规则,需要定义一个数组suffix[],其中suffix[i]=s表示 以i为边界,与模式串后缀匹配的最大长度,如下图所示,用公式表述:满足P[i-s,m]的最大长度.
计算后缀长度数组代码:
/**
* 计算后缀长度数组
* @param P 模式字符数组
* @return 后缀长度数组
*/
public static int[] suffix(char[] P) {
//初始化后缀数组
int m=P.length;
int []suffix=new int[m];
//计算后缀数组
suffix[m-1]=m;
for(int i=m-2;i>=0;--i) {
int q=i;
while(q>=0&&P[q]==P[m-1-i+q]) {
q--;
}
suffix[i]=i-q;
}
return suffix;
}
/**
* 好后缀忽略映射
* @param P 模式字符映射
* @return 后缀数组(字符对应模式字符数组中的最后位置)
*/
public static int[] bmgs(char[] P) {
//初始化忽略数组
int m=P.length;
int[] bmgs=new int[m];
//获取后缀数组
int[] suffix=suffix(P);
//赋值默认取值
Arrays.fill(bmgs, m);
//模式串中没有子串匹配上好后缀,但找到一个最大前缀
for (int i = m-1,j=0; i >=0; --i) {
if (suffix[i]==i+1) {
for (; j < m-1-i; ++j) {
if (bmgs[j]==m) {
bmgs[j]=m-1-i;
}
}
}
}
//模式串中有子串匹配上好后缀
for (int i = 0; i < m-2; ++i) {
bmgs[m-1-suffix[i]]=m-1-i;
}
return bmgs;
}
/**
* BM算法匹配
* @param T 正文字符数组
* @param P 模式字符数组
* @return 匹配位置
*/
public static int BM(char[] T,char[] P) {
//获取忽略映射
int []bmBc=bmBc(P);
int []bmGs=bmgs(P);
//匹配字符串
int j=0;
int n=T.length;
int m=P.length;
while(j<=n-m) {
int i=m-1;
while(i>=0&&P[i]==T[i+j]) {
i--;
}
//成功匹配字符
if (i<0) {
return j;
}
//往后移动位置
j+=Math.max(bmGs[i], bmBc[T[i+j]]-m+1+i);
}
return -1;
}
测试代码:
public static void main(String[] args) {
String text="HERE IS A SIMPLE EXAMPLE";
String pattern="EXAMPLE";
System.out.println(BM(text.toCharArray(),pattern.toCharArray()));
}