程序员的算法课(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

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: