字符串匹配算法

叁歲伎倆 2023-07-21 14:29 44阅读 0赞

### 目录 ###

*   *  BF
     *  KMP
     *   *  next数组
         *  匹配
         *  代码
     *  SunDay

## BF ##

*  最简单易懂的写法，也是性能最差的写法。
 *  最坏时间复杂度：`O(n*m)`

/** * @param str1 主串 * @param str2 子串 * @param pos 从主串的pos位置开始找. * @return */
        public static int BF(String str1,String str2,int pos) { 
            int lenstr1 = str1.length();
            int lenstr2 = str2.length();
            //对pos的位置合法判断
            if (pos < 0 || pos > lenstr1) { 
                return -1;
            }
            int i = pos;  //遍历主串，
            int j = 0;    //遍历子串
            while (i < lenstr1 && j < lenstr2) {   //主串和子串都没有遍历完成的情况下，比较字符是否相等
                if (str1.charAt(i) == str2.charAt(j)) {  //下标所对应的字符相等时，
                    i++;
                    j++;
                } else {    //匹配失败
                    i = i - j + 1; //主串从下一个字符开始匹配
                    j = 0;		   //子串从第一个字符开始匹配
                }
            }
            if (j >= str2.length()) {  //子串遍历完成则返回匹配成功时 i 的起始位置。
                return i - j;
            } else {    // 没找到
                return -1;
            }
        }

## KMP ##

*  主要分为两步，第一步，求`next`数组，第二步，匹配

### next数组 ###

*  `next`数组是对于一个字符串而言的，比如我们求`str2`在`str1`中是否存在，如果存在返回`str2`在`str1`中的起始索引，那么我们就要求出`str2`的`next`数组
 *  那字符串的`next`数组怎么求呢。
    
     *  假设字符串`abcabct`，对于`t`，它前面的字符串是`abcabc`，`abcabc`的前缀为`a`，`ab`，`abc`，`abca`，`abcab`；它的后缀`c`，`bc`，`abc`，`cabc`，`bcabc`(**前缀不能包含最后一位，后缀不能包含最前一位，所以前缀不能是`abcabc`，后缀也不能是`abcabc`**)。前缀与后缀中最长的相等的字符串是`abc`，所以`t`的`next`数组值为`abc`的长度，即为`3`。
     *  同理，对于`c`，它前面的字符串为`abcab`，前缀为`a`，`ab`，`abc`，`abca`；后缀为`b`，`ab`，`cab`，`bcab`。前缀与后缀中最长的相等的字符串是`ab`，所以`c`位置`next`数组值为`2`。
     *  倒数第`3`个字符`b`求法类推……
     *  对于最开始的`a`，由于它是第一个字符，前面没有字符串，所以人为规定它的`next`数组值为`-1`，也可以规定为`0`，但定为`-1`对后面有用，第二个字符`b`前面只有`a`，而前缀和后缀不能包含最后一个和第一个字符，所以第二个字符的`next`为`0`。除了第一个第二个特殊，其他的均用以上方法求`next`数组值
     *  所以，对于字符串`abcabct`，它的`next`数组值为`[-1,0,0,0,1,2,3]`

### 匹配 ###

*  得到`next`数组后怎么用呢?
 *  比如`str1`为`abcabckxyz`，`str2`为`abcabct`，显然是`k`和`t`不相等，而对于`str2`，`t`位置`next`数组值为`3`，所以就从`t`开始往前找`3`位，找到了`str2`中的第二个`a`，它对应`str1`中的第二个`a`，就将`str2`后移，使`str2`的起始位置元素对应`str1`中找到的这个元素。
 *  为什么这么做呢？
 *  首先，`k`和`t`不相等，说明`k`和`t`的前面都是相等的
    
     *  如图，`str1`从`i`位置开始，`str2`从`0`位置开始，进行匹配，到`X`、`Y`处发现不等，那么第一坨与第二坨肯定是相等的。并且**第一坨中任意一段一定与第二坨中对应段上的字符串相等。**  
        ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center]
 *  而`t`的`next`值表示`t`前面的串中最长的相等的前缀和后缀的长度
    
     *  如图，由上面加粗字体我们可以知道，第三坨字符串肯定与后缀段字符串相等，由`Y`位置的`next`数组值我们知道`Y`前面的串中最长的相等的前缀与后缀，也就是图中前缀段字符串与后缀段字符串相等，它们的长度就是`Y`位置的`next`数组值。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center 1]

*  所以，前缀段字符串与后缀段字符串相等，后缀段字符串与第三坨字符串相等，那么前缀段字符串就与第三坨字符串相等，那么我们就可以把第三坨字符串与前缀段字符串移到对应位置上，因为它们相等，所以下次匹配就从`X`位置和前缀字符串的后一个位置开始匹配。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center 2]

*  也就是将下图中的`X`位置与`Z`位置开始匹配，如果相同，分别匹配后一位，如果不相同，就采用上述方法，根据`Z`位置的`next`数组值，得到`Z`的前缀段字符串和后缀段字符串，这里不再赘述。
 *  如果`Z`位置的`next`数组值为`0`，说明`Z`前面的字符串没有相等的前缀段与后缀段，那么把`str2`的`0`位置与`str1`的`X`位置对齐即可。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center 3]

### 代码 ###

/** * 判断s1中是否存在s2，如果存在，返回匹配的起始索引，不存在返回-1 * @param s1 * @param s2 * @return */
        public static int getIndexOf(String s1,String s2){ 
            if(s1 == null || s2 == null || s2.length() < 1 || s1.length() < s2.length()){ 
                return -1;
            }
            char[] str1 = s1.toCharArray();
            char[] str2 = s2.toCharArray();
            // str1从i1位置开始，str2从i2位置开始，进行匹配
            int i1 = 0;
            int i2 = 0;
            // 得到next数组
            int [] next = getNextArray(str2);
            while (i1 < str1.length && i2 < str2.length){ 
                // 如果i1，i2位置的字符相同，i1，i2都后移
                if(str1[i1] == str2[i2]){ 
                    i1 ++;
                    i2 ++;
                }else{ // 如果i1，i2位置的字符不同，匹配失败
                    // i2的next数组值为-1(之前说了，第一个位置的next数组值人为规定为-1有用，就在这里用)，
                    // 说明i2是str2的开头，那么就从i1的下一个位置开始匹配
                    if(next[i2] == -1){ 
                        i1 ++;
                    }else{ 
                        // i2不是str2的开头，就把str2后移，后移多少呢，
                        // 要把i2的前缀段字符串与第三坨字符串移到对齐的位置，下次匹配时，从
                        // 前缀段字符串的后一个位置开始匹配，而i2就是表示从str2的哪个位置开始匹配，
                        // 并且前缀段字符串的长度为next[i2]，所以i2 = next[i2]，
                        i2 = next[i2];
                    }
                }
            }
            //i2 == str2.length，说明整个str2都匹配到了，否则返回-1
            return i2 == str2.length ? i1 - i2 : -1;
        }
    
        /** * 求next数组 * @param str * @return */
        private static int[] getNextArray(char[] str) { 
            if(str.length == 1){ 
                return new int[]{ -1};
            }
            int[] next = new int[str.length];
            //第一个字符的next数组值规定为-1，第二个字符的next数组值规定为0
            next[0] = -1;
            next[1] = 0;
            //从i开始，求[i,str.length)的next数组值
            int i = 2;
            // cn表示跳到的位置
            int cn = 0;
            while (i < next.length){ 
                //跳到的位置与i的前一个位置字符相同，那么next[i] = cn + 1
                if(str[i - 1] == str[cn]){ 
                    next[i ++] = ++cn;
                }else if(cn > 0){ 
                    cn = next[cn];
                }else{ 
                    next[i ++] = 0;
                }
            }
            return  next;
        }
    
        public static void main(String[] args) { 
            System.out.println(getIndexOf("abdefbcd","bcd"));
        }

## SunDay ##

public class TestSunDay { 
     
    	public static void main(String[] args) { 
    		
    		String source = "acfdedfacfdbea";
    		String target = "acfdbe";
     
    		int i = SunDay(source.toCharArray(),target.toCharArray(),0);
    		System.out.println("匹配结果：" + i);
    	}
    	
    	/** * * @param tempS 主串 * @param tempT 子串 * @param indexS 遍历主串是从indexS下标处开始遍历 * @return */
    	public static int SunDay(char[] tempS, char[] tempT,int indexS) { 
    		if(indexS >= tempS.length)
    			return -1;
    		//遍历子串是从indexT下标处开始遍历
    		int indexT = 0;
    		//计数匹配了多少个字符
    		int count = 0;
    		for (int i = indexS; i < indexS + tempT.length; i++) { 
    			if (tempS[i] == tempT[indexT]) { 
    				indexT ++;
    				count ++;
    			} else { 
    				break;
    			}
    		}
    		//匹配的字符数和子串的长度相等，即匹配成功
    		if (count == tempT.length) { 
    			return indexS;
    		}	
    		//匹配失败，看后面一个字符在子串中有没有相同的
    		if(indexS + tempT.length < tempS.length){ 
    			int i = check(tempS[indexS + tempT.length],tempT);
    			if( i == -1){ 
    				//没有相同的就子串就后移子串长度个位置
    				indexS += tempT.length;
    				//再重新匹配
    				return SunDay(tempS, tempT, indexS);
    			}else{ 
    				//后面一个字符在子串中有相同的,子串往后移若干位，使得这两个字符对其
    				indexS = indexS + tempT.length - i;
    				return SunDay(tempS, tempT, indexS);
    			}
    		}else{ 
    			return -1;
    		}
    	}
     
    	
    	/** * 判断在tempT数组中有没有c这个字符 * @param c * @param tempT * @return 返回c在tempT中的下标，没有就返回-1 */
    	public static int check(char c, char[] tempT) { 
    		for (int i = 0; i < tempT.length; i++) { 
    			if(c == tempT[i])
    				return i;
    		}
    		return -1;
    	}
    		
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/d8e1f806ab194506885ac761493c36f3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20230528/39e68dfe18b94a5b8ccf020a316342de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20230528/26314db0944f4364938ce23eca124a7d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNjA1OTEz_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20230528/9a940488e4b44f93800bea5a69fb4b4a.png