程序员的算法课（12）-使用通配符*,?等来查找字符串-程序员秋天

一、前言

相信大家都用过文本编辑器（EditPlus，notepad++，sublime..）、Word或者开发IDE工具（IDEA，Eclipse..）；甚至于你应该也写过不少SQL语句；你也用过百度、谷歌（怎么上谷歌我也不会，不要问我）搜过你要的内容。里面都会有个很重要的功能，那就是搜索，而搜索的方式中，对于通配符搜索我想大家也不会陌生。

【百度百科】通配符是一种特殊语句，主要有星号(*)和问号(?)，用来模糊搜索文件。当查找文件夹时，可以使用它来代替一个或多个真正字符；当不知道真正字符或者懒得输入完整名字时，常常使用通配符代替一个或多个真正的字符，其中，“?”可以代替一个字符，而“*”可以代替零个或多个字符。

二、通配符问题描述

题目描述：
Str1中可能包含的字符：任意字符串。（注意：字符串中可以带?*这样的通配符）
Str2中可能包含的字符：任意字符。其中，'?'表示匹配任意一个字符，'*'表示匹配任意字符0或者多次。
给出这样两个字符串，判断Str2是否是Str1的子串，如果是输出第一个匹配到的子串，如果不是，输出"不是子串"。

三、算法实现

1.正则表达式

import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class StringDemo {
    //使用正则表达式 通配符匹配字符串
    public static boolean isMatching(String src,String des){
        String des1 = des.replace("*", "\\w*");
        des1 = des1.replace("?", "\\w{1}");
        Pattern p = Pattern.compile(des1);
        Matcher m = p.matcher(src);
        return m.matches();
    }
}

这种方法是热身的，看上去也是最简单的，代码最少，也比较好理解，但在面试的时候可能不允许使用正则，他想让你分析下正则表达式的内部实现，那就尴尬了;而且，这个方法是有缺陷的，如果我们要查找的字符串中包含?*这样的字符，那就无法匹配，所以我们继续看下面的方法。

2.严格匹配（暴力匹配）

对于'?'的处理，只要在匹配的时候将代码由：if(str1[i]==str2[j]) 改为 if(str1[i]==str2[j] || str2[j]=='?')即可。
对于'*'的处理，可以将str2根据其中的'*'分为若干个片段，然后依次在str1中分别匹配这几个片段即可，而且对于这几个片段分别匹配，如果第k个片段在str1中匹配不到，后面也可以结束了。这里举例说明一下：对于str1="Oh year.Totay is weekend!"，str2=*ye*a*e*"，实际上就是在str1中匹配"ye","a","e"这三个片段。

    public static boolean isMatching2(String s, String p) {
        int i = 0;
        int j = 0;
        int starIndex = -1;
        int iIndex = -1;

        while (i < s.length()) {
            if (j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
                ++i;
                ++j;
            } else if (j < p.length() && p.charAt(j) == '*') {
                starIndex = j;
                iIndex = i;
                j++;//'*' can match 0 or above 0 characters
            } else if (starIndex != -1) {
                //such as "abggggb","*b"
                //so every time matching starts form the fisrt index of *
                //can avoid the case above
                j = starIndex + 1;
                i = iIndex+1;
                iIndex++;
            } else {
                return false;
            }
        }

        while (j < p.length() && p.charAt(j) == '*') {
            ++j;
        }

        return j == p.length();
    }

3.KMP算法

KMP本身不复杂，但网上绝大部分的文章把它讲混乱了。

【百度百科】KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

算法说明

设主串（下文中我们称作T）为：a b a c a a b a c a b a c a b a a b b

模式串（下文中我们称作W）为：a b a c a b

用暴力算法匹配字符串过程中，我们会把T[0] 跟 W[0] 匹配，如果相同则匹配下一个字符，直到出现不相同的情况，此时我们会丢弃前面的匹配信息，然后把T[1] 跟 W[0]匹配，循环进行，直到主串结束，或者出现匹配成功的情况。这种丢弃前面的匹配信息的方法，极大地降低了匹配效率。

而在KMP算法中，对于每一个模式串我们会事先计算出模式串的内部匹配信息，在匹配失败时最大的移动模式串，以减少匹配次数。

比如，在简单的一次匹配失败后，我们会想将模式串尽量的右移和主串进行匹配。右移的距离在KMP算法中是如此计算的：在已经匹配的模式串子串中，找出最长的相同的前缀和后缀，然后移动使它们重叠。

在第一次匹配过程中

T: a b a c a a b a c a b a c a b a a b b

W: a b a c a b

在T[5]与W[5]出现了不匹配，而T[0]~T[4]是匹配的，其中T[0]~T[4]就是上文中说的已经匹配的模式串子串，移动找出最长的相同的前缀和后缀并使他们重叠：

T: a b a c aa b a c a b a c a b a a b b

W: a b a c a b

然后在从上次匹配失败的地方进行匹配，这样就减少了匹配次数，增加了效率。

    static boolean isEmpty(final String str) {
        return str == null || str.isEmpty();
    }

    // str may contain '?'
    static int[] getNextArray(final String str) {
        if (isEmpty(str)) {
            return null;
        }
        int[] next = new int[str.length()];
        int k = -1;
        int j = 0;
        next[0] = -1;
        while (j < str.length() - 1) {
            if (k == -1 || str.charAt(k) == str.charAt(j) || str.charAt(k) == '?' || str.charAt(j) == '?') {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
        return next;
    }

    // pattern may contain '?'
    static int kmpFind(final String str, final String pattern, int start) {
        if (isEmpty(str)) {
            return -1;
        }
        int[] next = getNextArray(pattern);
        if (next == null) {
            return -1;
        }
        int i = start;
        while (i < str.length()) {
            int j = 0;
            while (j < pattern.length()) {
                if (str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '?') {
                    i++;
                    j++;
                } else {
                    break;
                }
            }
            i -= j;
            if (j == pattern.length()) {
                return i;
            }
            int move = j - next[j];
            i += move;
        }
        return -1;
    }

4.KMP算法扩展

    // pattern may contain '*' and '?'
    // pattern按*分割后，子串里可能含有?,没法用String.find, 所以针对含?的字符串，
    // 结合KMP算法，实现了find函数，之后再将pattern按*分割，
    // 在输入字符串中按顺序查找子串，已实现find含有*和?的字符串
    static int find(final String str, final String pattern) {
        if (isEmpty(str)) {
            return -1;
        }
        if (isEmpty(pattern)) {
            return -1;
        }
        String[] items = pattern.split("\\*");
        int i = 0;
        int ret = -1;
        for (String s : items) {
            int index = kmpFind(str, s, i);
            if (index < 0) {
                return -1;
            }
            if (i == 0) {
                ret = index;
            }
            i = index + s.length();
        }
        return ret;
    }

我的微信公众号：架构真经（id：gentoo666），分享Java干货，高并发编程，热门技术教程，微服务及分布式技术，架构设计，区块链技术，人工智能，大数据，Java面试题，以及前沿热门资讯等。每日更新哦！

参考资料：

1、 https://www.cnblogs.com/pangxiaodong/archive/2011/09/07/2169588.html；
2、 https://bbs.csdn.net/topics/390941031；
3、 https://www.iteye.com/blog/sunlujing-1706919；
4、 https://www.jianshu.com/p/15865bac6a1b；
5、 https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html；
6、 https://baike.baidu.com/item/kmp%E7%AE%97%E6%B3%95/10951804?fr=aladdin；