AcWing 3528. 字符串匹配(小白推荐看的思路)
原题链接
简单
作者:
致敬大佬
,
2024-07-26 02:18:32
,
所有人可见
,
阅读 14
题目描述略
这个题解是在我刚学完语法基础课字符串基本操作的时候写的,所以是很暴力但也很简单
直接的做法,对我这种刚入门算法的小白比较友好。下面先上代码,再讲思路:
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1010;
int n;
string s[N];
string p;
int cnt1, cnt2;
string m[N];
int main()
{
cin >> n;
for (int i = 0; i < n; i ++) cin >> s[i];
cin >> p;
//将p拆分为各个模式子串,存到字符串数组m[N]中
int left[N], right[N];
bool in = false;
int idx = 0;
for (int i = 0; p[i]; i ++)
{
if (p[i] == '[') in = true, left[cnt1++] = i;
else if (p[i] == ']')
{
idx ++, in = false, right[cnt2++] = i;
m[idx - 1] = p.substr(left[cnt1 - 1] + 1, right[cnt1 - 1] - left[cnt1 - 1] - 1);
}
else if (!in)
{
idx ++, m[idx - 1] = p[i];
}
}
// 开始匹配
bool out = false;
bool found = false;
for (int i = 0; i < n; i ++)
{
if (s[i].size() != idx) continue;
for (int j = 0; s[i][j]; j ++)
{
int k = 0;
while(k < m[j].size() && tolower(s[i][j]) != tolower(m[j][k])) k++;
if (k == m[j].size())
{
out = true;
break;
}
else
{
found = true;
break;
}
}
if (out) continue;
else if (found)
{
cout << i + 1 << ' ' << s[i] << endl;
continue;
}
}
return 0;
}
我的切入点是,如果这个题可以将含有正则匹配的串P转化为一个字符串数组m[N],m[i]存
打开了[]的结果,比如:[bc]a[a2b]b 变为 m[0] = bc, m[1] = a, m[2] = a2b, m[3] = b
以此类推,那问题不就变成了单个字符与字符串数组中的每个字符串进行匹配吗?
(单个字母也算一个字符串)那写个循环就行了。考虑到数据量不大,这种暴力解法应该
能过。