【校招VIP】字符串匹配算法- 校招VIP

转载声明：文章来源https://blog.csdn.net/qq_66478305/article/details/140145870

字符串匹配算法是在一个字符串（称为文本）中查找另一个字符串（称为模式）出现的位置或者是否存在的算法。

暴力匹配（Brute Force）
从主串的每一个可能的位置开始，依次比较主串中的子串与模式串是否匹配。如果匹配成功，则返回匹配的位置；否则，继续尝试下一个位置。
1、从主串的第一位开始，将主串与模式串的字符逐个比较

2、将模式串后移一位，从主串的第二位开始，将主串与模式串的字符逐个比较

3、直到主串的子串与模式串的所有字符都匹配，则匹配成功

BF算法的实现比较简单，但效率较低，时间复杂度为O(mn)

bool BFfind(string str1, string str2)
{
	for (int i = 0; i < str1.size() - str2.size() + 1; i++)
	{
		int j = 0;
		for (; j < str2.size(); j++)
		{
			if (str1[i+j] != str2[j])
			{
				break;
			}
		}
		if (j >= str2.size())
		{
			return true;
		}
	}
	return false;
}

Rabin-Karp算法
BF算法在每次检查子串和模式串是否匹配的时候，需要依次对比每个字符，比较耗时。因为哈希值是一个数字，比较数字是否相等是非常快速的，可以提高模式串与子串的比对效率，所以通过增加哈希算法，来加快子串与模式串的匹配。
对主串中n-m+1个子串和模式串求哈希值，然后比较子串的哈希值和模式串的哈希值，如果不相等证明不匹配，如果相等就匹配（没有哈希冲突的情况）。它适用于在一段文本中搜索多个不同的模式串。

生成哈希值的方法有很多：
按位相加：
将a当作1，b当作2...然后将字符串的所有字符相加，相加结果就是它的哈希值。比如：def=4+5+6=15，这个哈希算法简单，但是发生哈希冲突的概率很大。比如：def和edf，def的哈希值一样。
1、生成模式串的哈希值，生成主串中第一个等长子串的哈希值

2、哈希值相等，逐个字符比较，不相等，继续

加快计算速度

转换为K进制数
假设主串和模式串对应的字符集只包含K个字符，我们可以用一个K进制数来表示一个子串，把K进制数转换为十进制数，作为子串的哈希值。
比如字符串只包含26个小写字母，可以将每个字符串当成一个26进制数来计算。
def=4*(26^2)+5*26+6=2840
这么做可以大幅减少hash冲突，缺点是计算量比较大，而且可能会超出整数范围

相邻子串s[i-1]和s[i]对应的哈希值计算公式有交集，也就是说，我们可以使用s[i-1]的哈希值快速的计算出s[i]的哈希值。这种利用前一次计算的哈希值来更新当前子串的哈希值，以便在子串滑动到下一个位置时不需要重新计算整个子串的哈希值的方法叫做滚动哈希。
因为哈希值过大会造成溢出，所以我们可以在计算过程中还要对结果取模。取模的值应该尽可能大，并且应该是质数，这样才能减少哈希碰撞的概率。

int RKfind(string& str1, string& str2)
{
	int m = str1.size() - str2.size()+ 1;
	int str2hash = 0;
	int str1hash = 0;
	for (int i = 0; i < str2.size(); i++)
	{
		str2hash += (str2[i] - 'a') * pow(26, str2.size() - i - 1);
		str1hash += (str1[i] - 'a') * pow(26, str2.size() - i - 1);
	}
	for (int i = 0; i < m; i++)
	{
		if (str1hash == str2hash)
		{
			int j = 0;
			for (; j < str2.size(); j++)
			{
				if (str1[j + i] != str2[j])
				{
					break;
				}
			}
			if (j == str2.length())
			{
				return i;
			}
		}
		str1hash = (str1hash - (str1[i] - 'a') * pow(26, str2.size() - 1)) * 26 + (str1[i + str2.size()] - 'a');
	}
	return -1;
 
}

滚动哈希是一种针对固定长度的滑动窗口的哈希方法。通过滚动哈希算法，可以将每次计算子串哈希值的复杂度从O(m) 降到了O(1)，可以显著提高字符串搜索的效率，尤其是在处理长文本时。它可以在O(n+m)时间内完成字符串匹配。
RK 算法可以看做是 BF 算法的一种改进。在 RK 算法中，判断模式串的哈希值与每个子串的哈希值之间是否相等的时间复杂度为 O(1)。总共需要比较n−m+1 个子串的哈希值，所以 RK 算法的整体时间复杂度为 O(n)。跟 BF 算法相比，RK 算法的效率提高了很多。
但是如果存在冲突的情况下，算法的效率会降低。最坏情况是每一次比较模式串的哈希值和子串的哈希值时都相等，但是每一次都会出现冲突，那么每一次都需要验证模式串和子串每个字符是否完全相同，那么总的比较次数就是 m×(n−m+1)，时间复杂度就会退化为 O(m×n)。
BM算法
BM算法规定了两个规则：坏字符规则和好后缀规则。
这两种启发策略的计算过程只与模式串 p 相关，而与主串无关。因此在对模式串 p 进行预处理时，可以预先生成「坏字符规则后移表」和「好后缀规则后移表」，然后在匹配的过程中，只需要比较一下两种策略下最大的后移位数进行后移即可。
BM 算法在移动模式串的时候和常规匹配算法一样是从左到右进行，但是在进行比较的时候是从右到左，即基于后缀进行比较。
坏字符
坏字符是指模式串与子串当中不匹配的字符。
当子串中某个字符跟模式串的某个字符不匹配时，则称子串中这个失配字符为「坏字符」，此时模式串可以快速向右移动。

上述这个空格为坏字符。
当出现坏字符之后，因为只有 [模式串与坏字符对齐的位置] 等于坏字符的情况下，两者才有匹配的可能。
当坏字符没有在模式串出现时：
向右移动位数 = 坏字符在模式串中的失配位置 + 1。

当坏字符出现在模式串时：
向右移动位数 = 坏字符在模式串中的失配位置 - 坏字符在模式串中最后一次出现的位置。

坏字符的位置越靠右，下一轮模式串的挪动跨度越大，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。

vector<int> getBadChar(string& str)
{
    vector<int> nums(26,-1);
	//查找模式串的字母的最后出现位置
	for (int i = 0; i < str.size(); i++)
	{
		nums[str[i] - 'A'] = i;
	}
	return nums;
}

好后缀
好后缀是指模式串和子串当中相匹配的后缀。
好后缀规则（The Good Suffix Shift Rule）
当子串中某个字符跟模式串的某个字符不匹配时，则称子串中已经匹配好的字符串为「好后缀」，此时模式串可以快速向右移动。

1、如果模式串中存在子串匹配上好后缀，则把子串与好后缀对齐，然后从模式串的最尾元素开始往前匹配。
向右移动位数 = 好后缀的最后一个字符在模式串中的位置 - 匹配的子串最后一个字符出现的位置。

2、如果无法从模式串中找到与「好后缀」相匹配的子串，则在模式串中查找与「好后缀的后缀子串」相匹配的最长的前缀，让子串与最长的前缀对齐（如果这个前缀存在的话）
向右移动位数 = 好后缀的后缀的最后一个字符在模式串中的位置 - 最长前缀的最后一个字符出现的位置。

3、模式串中无子串匹配上好后缀，也找不到前缀匹配
向右移动位数 = 模式串的长度。

生成好后缀移位表
１、生成辅助好后缀数组
suffix[i] 表示为以下标 i 为结尾的子串与模式串后缀匹配的最大长度
用公式可以描述为：即满足 P[i−s...i]==P[m−1−s,m−1] 的最大长度为 s，ｍ为模式串的长度
从当前索引i开始，尝试向前找到与模式串末尾相同的最长字符序列。
如果找到不匹配的字符，停止向前搜索，并计算当前匹配的长度：i - start。

２．构建后缀数组bmGs[]：bmGs[i]表示遇到好后缀时，模式串应该右移的距离，其中ｉ表示当前匹配失效时的字符位置（即当前坏字符的位置）
BM算法代码

vector<int> getBadChar(string& str)
{
	vector<int> nums(256, -1);
	//查找模式串的字母的最后出现位置
	for (int i = 0; i < str.size(); i++)
	{
		nums[str[i] - 'A'] = i;
	}
	return nums;
}
vector<int> getSuffix(string& str)
{
	int m = str.size();
	vector<int> suffix(m, m);
 
	for (int i = m - 2; i >= 0; i--)
	{
		int start = i;
		while (start >= 0 && str[start] == str[m - 1 - i + start])
		{
			--start;
		}
		suffix[i] = i - start;
	}
	return suffix;
}
 
vector<int> getBmGs(string& str)
{
    int m = str.size();
    //情况 3: 模式串中无子串匹配上好后缀，也找不到前缀匹配
    vector<int> bmGs(m, m);
 
    vector<int> suffix = getSuffix(str);
    //情况2，模式串中无子串匹配上好后缀，但有最长前缀匹配好后缀的后缀
    for (int i = m - 1; i >= 0; i--)
    {
        //[0,i]范围的前缀与后缀匹配
        if (suffix[i] == i + 1)
        {
            for (int j = 0; j < m - 1 - i; j++)
            {
                //如果不等于m，代表存在前缀更长的匹配，在前几轮已经被修改过了
                if (bmGs[j] == m)
                {
                    bmGs[j] = m - 1 - i;
                }
            }
        }
    }
    //情况 1，模式串中有子串匹配上好后缀
    for (int i = 0; i < m - 1; i++) {
        bmGs[m - 1 - suffix[i]] = m - 1 - i;
    }
    return bmGs;
}
 
int BMfind(string& str1, string& str2)
{
	 vector<int> bcnums = getBadChar(str2);
	 vector<int> gsnums = getBmGs(str2);
	 int i = 0;
	 while (i < str1.size() - str2.size() + 1)
	 {
		 int j = str2.size() - 1;
		 for (; j >= 0 && str1[i + j] == str2[j]; j--);
 
		 //表示整个模式串都匹配成功
		 if (j < 0) {
			
			 return i;
		 }
         //获取坏字符的移动长度
		 int len= bcnums[str1[i + j] - 'A'] == -1?j+1: j - bcnums[str1[i + j] - 'A'];
         //比较好后缀和坏字符的移动长度
		 i +=max(len, gsnums[j]);
 
 
	 }
	 return -1;
}

注：以上的测试案例为大写字母范围，如果需要字符集包含其他字符比如空格，小写的，需要修改坏字符相关代码

KMP算法
KMP算法通过预处理模式串构建部分匹配表（也称为next数组），然后在匹配过程中根据部分匹配表来移动模式串，避免重复比较已经匹配的部分。时间复杂度为O(m+n)，其中m为文本长度，n为模式长度。
对于给定主串T 与模式串 p，当发现主串T 的某个字符与模式串 p 不匹配的时候，可以利用匹配失败后的信息，尽量减少模式串与文本串的匹配次数，避免文本串位置的回退，以达到快速匹配的目的。
当子串与模式串不匹配时，BF算法选择移动到下一个位置，但这样子做要比对很多次，为了加快查询是否可以利用这些已知的信息来加快查询

我们能很快反应应该将模式串的第一个AB移动到子串的不匹配字符前的AB的位置，因为我们想要在主串的后面找到与模式串前面相同的地方，可以理解为在子串的后缀数组中找到与模式串的前缀数组相等的最长匹配，因为不匹配字符前的子串是相同的，我们可以转化为找到模式串的匹配字符串的前缀与后缀的最长匹配

生成next数组
next[ｉ] 表示的含义是：记录下标ｉ之前的模式串p 中，最长相等前后缀的长度。即在下标ｉ发生失配时，他前面的子串的最长相等前后缀的长度。
黄色箭头表示在模式字符串中已经匹配的部分的结束位置，初始化为-1，下标０发生失配时，匹配字符串为空，初始化为－１

下标１发生失配时，它的匹配字符串是Ａ，前缀和后缀不能是字符串本身，所以它的最长相等为０

下标为２时，比较黄色箭头与蓝色箭头指向的字符，不一致，因为黄色箭头表示在模式字符串中已经匹配的部分的结束位置，现在不一致，将黄色箭头赋值为next[黄色箭头的位置],即-1
next［２］＝０

下标为５时，黄色箭头前面的字符表示上一轮中匹配字符串的最长相等前后缀的子串，当黄色箭头和蓝色箭头指向的字符相等，next［５］＝黄色箭头前面的字符串长度＋１，同时如果我们想要在下一轮中获得更长的前后缀子串，我们就需要将黄色箭头移动到下一个位置

vector<int> getNext(string p)
{
    vector<int> next(p.size());
    next[0]=-1;
    int j=0;
    int k=-1;
    while(j<p.size()-1)
    {
        if(k==-1||p[j]==p[k])
        {
            k++;
            j++;
            next[j]=k;
        }else{
            k=next[k];
        }
    }
    return next;
}

int KMP(string s,string p)
{
    int i=0;
    int j=0;
    vector<int> next=getNext(p);
 
    while(i<s.size()&&j<p.size())
    {
        if(j==-1||s[i]==p[j])
        {
            i++;
            j++;
        }else{
            j=next[j];
        }
    }
    if(j==p.size())
    {
        return i-j;
    }
    return -1;
}