字符串匹配问题
给你两个仅包含小写字母的字符串：主串 S = "abcacabdc"、模式串 T = "abd"，请查找出模式串在主串第一次出现的位置。在这题中答案是 6。
备注：主串和模式串均为小写字母且都是合法输入，代码中不用考虑字符串的异常情况。
BF算法
BF算法，即暴力(Brute Force)算法，是普通的模式匹配算法，BF算法的思想就是将目标串 S 的第一个字符与模式串 T 的第一个字符进行匹配，若相等，则继续比较 S 的第二个字符和 T 的第二个字符；若不相等，则比较 S 的第二个字符和 T 的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法，时间复杂度为 O(m*n)。
思路：
- 分别利用计数指针 i 和 j 指示主串 S 和模式 T 中当前待比较的字符位置，i 和 j 的初值为1;
- 如果 2 个串都没有比较到串尾，即 i 和 j 均小于等于 S 和 T 的长度时, 则循环执行以下的操作:
- S[i] 和 T[j] 比较，若相等：则 i 和 j 分别指示主串和模式串中下一个位置，继续比较后续的字符;
- 若不相等，指针后退重新开始匹配。从主串的下一个字符串(i = i - j + 2)起再重新和模式串第一个字符(j = 1)比较;
- 如果 j > T.length，说明模式T中的每个字符串依次和主串S找中的一个连续字符序匹配成功，返回和模式T中第一个字符的字符在主串S中的序号 (i-T.length); 否则匹配失败,返回-1;
备注：字符串的下标0中存储的是字符的长度。
代码如下：
int getIndex_BF(String strOne, String strTwo){
int i = 1;
int j = 1;
//判断两个字符串是否比到尾了
while (i <= strOne[0] && j <= strTwo[0] ) {
//比较两个字符是否相等
if (strOne[i] == strTwo[j]) {
//相等则继续比较下一个
I++;
j++;
}
else {
//不相等则从主串此次比较的下个位置继续比较
i -= (j - 2);
//模式串要从头开始
j = 1;
}
}
//如果j大于模式串的长度，说明找到了模式串，位置在i-模式串长度的地方
if (j > strTwo[0]) {
return i - strTwo[0];
}
return -1;
}
RK算法
RK 算法的全称叫 Rabin-Karp 算法。它是由两位发明者 Rabin 和 Karp 的名字来命名的算法，这个算法理解不算过于复杂，但是有一些编码技巧在里面，可以让我们学习。
在刚刚学习的BF算法中，如果模式串长度为 m，主串长度为 n，那在主串中就会有 n-m+1 个长度为 m 的子串。我们只需要暴力地对比这 n-m+1 个子串与模式串，就可以找出主串与模式串匹配的子串。但是每次检查主串的子串与模式串是否匹配, 需要依次比对每个字符, 所以BF算法的时间复杂度比较高，是O(n*m)。我们对BF的字符串匹配算法稍加改造，引入哈希算法，时间复杂度立刻就会降低。
RK 算法的思路是这样的：我们通过哈希算法对主串中的 n-m+1 个子串分别求哈希值，然后逐个与模式串的哈希值比较大小。如果某个子串的哈希值与模式串相等，那就说明对应的子串和模式匹配了。
在讲思路前我先讲下这里我使用的Hash算法：
- 计算字符串的（每个字符的Ascii码值 - 'a'的Ascii码值 + 1），我称之为Value;
- 将每个Value相乘，得到字符串的Hash值。
这个Hash算法不太好，会出现哈希冲突。大家自己可以设计不会出现冲突又好计算的Hash算法，在这里提一下，使用26进制Hash算法模式串一长就会造成Hash值超过long long类型的最大值，所以它也可能出现哈希冲突。
时间复杂度：
- 使用不会冲突的算法：O(n)；
- 使用会冲突的的Hash算法：O(m+n)，但是平均复杂度比BF算法好。
RK算法思路：
- 记录两个字符串的长度；
- 计算模式串的Hash值；
- 依次计算出主串每个子串的Hash值，边计算边比较，不要全部计算好再比较；
- 在计算新子串的Hash值时可以根据旧子串的Hash计算得出，减少重复计算；
- Hash值相同需对比一下子串和模式串是否匹配（防止出现哈希冲突），匹配则返回index；
- 如果没有找到匹配的子串，则返回-1。
代码如下：
//RK算法
int getIndex_RK(String strOne, String strTwo){
//1、记录两个字符串的长度
int lengthOne = strOne[0];
int lengthTwo = strTwo[0];
//2、计算模式串的Hash值
long long twoHashValue = 1;
for (int i = 1; i <= lengthTwo; i++) {
int value = strTwo[i] - 'a' + 1;
twoHashValue *= value;
}
//3、依次计算出主串每个子串的Hash值，边计算边比较
long long oneHashValue = 1;
for (int i = 1; i <= lengthOne - lengthTwo + 1; i++) {
if (i == 1) {
for (int j = 1; j <= lengthTwo; j++) {
int value = strOne[j] - 'a' + 1;
oneHashValue *= value;
}
}
else {
//4、计算新子串的Hash值可以根据旧子串的Hash计算得出，减少重复计算
int valueOld = (strOne[i - 1] - 'a' + 1);
int valueNew = (strOne[i + lengthTwo - 1] - 'a' + 1);
oneHashValue = oneHashValue / valueOld * valueNew;
}
//5、Hash值相同需对比一下子串和模式串是否匹配（防止出现哈希冲突），匹配则返回index
if (oneHashValue == twoHashValue) {
int isOK = isMatch(strOne, i, strTwo);
if (isOK == 1) {
return I;
}
}
}
//6、如果没有找到匹配的子串，则返回-1
return -1;
}
//判断Hash值相等的字符串是否相等
int isMatch(String strOne, int index, String strTwo){
for (int i = 1; i <= strTwo[0]; i++) {
if (strOne[index + i - 1] != strTwo[i]) {
return 0;
}
}
return 1;
}
辅助代码
#include "string.h"
#define OK 1
#define ERROR 0
typedef int Status;
#define MAX_SIZE 100
//定义串，0号单元存放串的长度
typedef char String[MAX_SIZE +1];
//生成一个其值等于chars的串
Status assignStr(String str, char *chars){
int length = (int)strlen(chars);
if (length > MAX_SIZE) {
return ERROR;
}
str[0] = length;
for (int i = 1; i <= length; i++) {
str[i] = chars[i - 1];
}
return OK;
}
//打印字符串
void printfStr(String str){
for (int i = 1; i <= str[0]; i++) {
printf("%c",str[I]);
}
printf("\n");
}
int main(int argc, const char * argv[]) {
char *charsOne = "ssadfaadfsa";
String strOne;
assignStr(strOne, charsOne);
printf("主串为：");
printfStr(strOne);
char *charsTwo = "fsa";
String strTwo;
assignStr(strTwo, charsTwo);
printf("模式串为：");
printfStr(strTwo);
printf("第一次出现模式串的索引位置为：\n");
int indexBf = getIndex_BF(strOne, strTwo);
printf("BF算法：%d\n",indexBf);
int indexRk = getIndex_RK(strOne, strTwo);
printf("RK算法：%d\n",indexRk);
return 0;
}
执行结果
