一、前言

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

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

二、通配符问题描述

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

三、算法实现

1.正则表达式

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

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

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"这三个片段。

1.  
   public static boolean isMatching2(String s, String p) {
2.  
   int i = 0;
3.  
   int j = 0;
4.  
   int starIndex = -1;
5.  
   int iIndex = -1;
6.  
    
7.  
   while (i < s.length()) {
8.  
   if (j < p.length() && (p.charAt(j) == ‘?‘ || p.charAt(j) == s.charAt(i))) {
9.  
   ++i;
10.  
    ++j;
11.  
    } else if (j < p.length() && p.charAt(j) == ‘*‘) {
12.  
    starIndex = j;
13.  
    iIndex = i;
14.  
    j++;//‘*‘ can match 0 or above 0 characters
15.  
    } else if (starIndex != -1) {
16.  
    //such as "abggggb","*b"
17.  
    //so every time matching starts form the fisrt index of *
18.  
    //can avoid the case above
19.  
    j = starIndex + 1;
20.  
    i = iIndex+1;
21.  
    iIndex++;
22.  
    } else {
23.  
    return false;
24.  
    }
25.  
    }
26.  
     
27.  
    while (j < p.length() && p.charAt(j) == ‘*‘) {
28.  
    ++j;
29.  
    }
30.  
     
31.  
    return j == p.length();
32.  
    }

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

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

1.  
   static boolean isEmpty(final String str) {
2.  
   return str == null || str.isEmpty();
3.  
   }
4.  
    
5.  
   // str may contain ‘?‘
6.  
   static int[] getNextArray(final String str) {
7.  
   if (isEmpty(str)) {
8.  
   return null;
9.  
   }
10.  
    int[] next = new int[str.length()];
11.  
    int k = -1;
12.  
    int j = 0;
13.  
    next[0] = -1;
14.  
    while (j < str.length() - 1) {
15.  
    if (k == -1 || str.charAt(k) == str.charAt(j) || str.charAt(k) == ‘?‘ || str.charAt(j) == ‘?‘) {
16.  
    k++;
17.  
    j++;
18.  
    next[j] = k;
19.  
    } else {
20.  
    k = next[k];
21.  
    }
22.  
    }
23.  
    return next;
24.  
    }
25.  
     
26.  
    // pattern may contain ‘?‘
27.  
    static int kmpFind(final String str, final String pattern, int start) {
28.  
    if (isEmpty(str)) {
29.  
    return -1;
30.  
    }
31.  
    int[] next = getNextArray(pattern);
32.  
    if (next == null) {
33.  
    return -1;
34.  
    }
35.  
    int i = start;
36.  
    while (i < str.length()) {
37.  
    int j = 0;
38.  
    while (j < pattern.length()) {
39.  
    if (str.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == ‘?‘) {
40.  
    i++;
41.  
    j++;
42.  
    } else {
43.  
    break;
44.  
    }
45.  
    }
46.  
    i -= j;
47.  
    if (j == pattern.length()) {
48.  
    return i;
49.  
    }
50.  
    int move = j - next[j];
51.  
    i += move;
52.  
    }
53.  
    return -1;
54.  
    }

4.KMP算法扩展

1.  
   // pattern may contain ‘*‘ and ‘?‘
2.  
   // pattern按*分割后，子串里可能含有?,没法用String.find, 所以针对含?的字符串，
3.  
   // 结合KMP算法，实现了find函数，之后再将pattern按*分割，
4.  
   // 在输入字符串中按顺序查找子串，已实现find含有*和?的字符串
5.  
   static int find(final String str, final String pattern) {
6.  
   if (isEmpty(str)) {
7.  
   return -1;
8.  
   }
9.  
   if (isEmpty(pattern)) {
10.  
    return -1;
11.  
    }
12.  
    String[] items = pattern.split("\\*");
13.  
    int i = 0;
14.  
    int ret = -1;
15.  
    for (String s : items) {
16.  
    int index = kmpFind(str, s, i);
17.  
    if (index < 0) {
18.  
    return -1;
19.  
    }
20.  
    if (i == 0) {
21.  
    ret = index;
22.  
    }
23.  
    i = index + s.length();
24.  
    }
25.  
    return ret;
26.  
    }

我的微信公众号：架构真经（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