题目描述
读入一个字符串数组string[]，再读入一个短字符串。要求查找string[]中和短字符串的所有匹配，输出行号和匹配的字符串以。匹配时不区分大小写，并且可以有一个中括号表示的模式匹配。例如，对aa[123]bb来说，aa1bb，aa2bb，aa3bb都算匹配。
输入格式：
第一行输入字符串数组的长度
接下来几行输入字符串，作为主串
最后输入模式串
输出格式：
若干行，每一行由行号和匹配的字符串组成
样例：
输入：
2
daa1bb
daa2bb
aa[123]bb
输出：
1 aa1bb
2 aa2bb
使用C++ string库下的函数解决
算法思想
首先找到中括号里面的内容，记为brackets，对pattern字符串进行如下处理：首先将[]里面的内容替换为空，接下来依次将中括号里面的字符插入到pattern串中被替换的位置。再依次进行匹配，在匹配的时候需要注意不区分大小写，实际上就是多加一个判断条件。
c++ 算法描述
#include <iostream>
#include <string>
using namespace std;
string pattern;
string *text;
int length;// 测试主串的数目
/**
使用C++自带的函数实现
*/
void kmp()
{
/*
思路一：使用C++自带的一些函数
将pattern分解成正常的匹配格式：
a[123]b===>a1b,a2b,..
*/
int start = pattern.find('[');
int end = pattern.find(']');
string brackets = pattern.substr(start, end - start + 1); // 括号里面的内容
pattern.replace(start, end - start + 1, "");
// 轮流替换
for (int i = 0; i < length; i++)
{
for (int j = 1; j + 1 < brackets.length(); j++)
{
// 注意不区分大小写，因此对于模式串
/*
aa[a]bb需要查两次，分别是aaAbb和aaabb
*/
if (brackets[j] >= 'a' && brackets[j] <= 'z')
{
pattern.insert(start, 1, brackets[j] - 32);
}
if (brackets[j] >= 'A' && brackets[j] <= 'Z')
{
pattern.insert(start, 1, brackets[j] + 32);
}
// 上面的两个if只有一个可以执行
if (text[i].find(pattern) != string::npos)
{
cout << i + 1 << " " << pattern << endl;
}
pattern.replace(start, 1, "");
pattern.insert(start, 1, brackets[j]);
if (text[i].find(pattern) != string::npos)
{
cout << i + 1 << " " << pattern << endl;
}
pattern.replace(start, 1, "");
}
}
}
int main()
{
cin >> length;
text = new string[length];
for (int i = 0; i < length; i++)
{
cin >> text[i];
}
cin >> pattern;
// 函数处理
kmp();
}
测试结果
时间复杂度分析
输入n组测试数据，模式串的长度为m，其中括号里面包含的元素的个数为
p，时间复杂度为O(p*(m+n))，其中c++里面find函数查找时间复杂度为O(m+n)，如果是在考试中，我肯定就这样写了。时间复杂度也可以接收，因为一般括号里面的内容比较短。
使用改进版的kmp算法
算法思想
在原有kmp算法的基础上，实际上就是加入了两种特殊的情况：
- 不区分大小写
- 模式串存在多种匹配可能
因此只需要处理好上面的两种特殊情况，实际也可以解决这个问题。
其基本思路为，先对模式串处理，去掉[]里面的内容，包括中括号，使用通配符 * 代替。通配符之前的元素可以正常使用原来的kmp算法，关键就是通配符后面的元素。
生成next数组
- 通配符 * 前面的元素按照原来算法进行，通配符后面的元素，分两种情况处理：记通配符的位置为start。
匹配
算法描述
#include <iostream>
#include <string>
using namespace std;
string pattern;
string *text;
int length; // 测试主串的数目
// 处理两种特殊的相等
// 判断brackets里面上是否包含t，如果t是字母，判断是否包含其大小写
bool isEqual(string brackets, char t)
{
if (brackets.find(t) != string::npos)
{
return true;
}
else
{
if (t >= 'a' && t <= 'z')
{
return brackets.find(char(t - 32)) != string::npos;
}
if (t >= 'A' && t <= 'Z')
{
return brackets.find(char(t + 32)) != string::npos;
}
}
return false;
}
/**
* @brief 不区分大小写情况判断两个字符是否相等
*
* @param i
* @param j
* @return true
* @return false
*/
bool isEqual(char i, char j){
if (i == j)
return true;
if (i < 65 || j < 65)
{
return false;
}
if (i > 97 || j > 97)
return false;
return abs(i - j) == 32;
}
/**
* @brief 改进版的kmp模式匹配
*
*/
void kmp2()
{
// 将形如 aa[123]bb替换为aa*bb
int start = pattern.find('[');
int end = pattern.find(']');
string brackets = pattern.substr(start, end - start + 1); // 括号里面的内容
pattern.replace(start, end - start + 1, "*");
// 初始化next数组
int next_length = pattern.length();
int *next = new int[next_length];
int i = 0;
int j = -1;
next[0] = -1;
while (i < next_length)
{
if (j == -1 ||
(j == start && isEqual(brackets, pattern[i])) || // 特殊情况一，j为通配符，此时pattrn[j]的值属于中括号里面的内容，需要分别匹配
(j != start && isEqual(pattern[i], pattern[j])) ||
(i == start && isEqual(brackets, pattern[j]))) // 特殊情况2，求解next[start+1]
{
i++;
j++;
// 匹配的情况
next[i] = j;
}
else
{
j = next[j];
}
}
// 打印next数组
// for (int i = 0; i < next_length; i++)
// {
// printf("%d ", next[i]);
// }
// printf("\n");
// 开始匹配
for (int len = 0; len < length; len++)// len组测试数据
{
// 进行模式匹配
i = 0;
j = 0;
while (j < next_length && i < text[len].length())
{
if (j == -1 ||
(j != start && isEqual(text[len][i], pattern[j])) ||
(j == start && isEqual(brackets, text[len][i])))
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == next_length)
{
cout << len + 1 << " " << text[len].substr(i - j, j) << endl;
}
}
}
int main()
{
cin >> length;
text = new string[length];
for (int i = 0; i < length; i++)
{
cin >> text[i];
}
cin >> pattern;
// 函数处理
// kmp();
kmp2();
}
测试结果
