我试图只使用数组来解决一个非常基本的问题(文本是字符的数组),但在实现某些特定的东西时遇到了问题。
因此,我尝试编写一个函数,该函数以两个字符数组(即text和pattern)为参数,并返回该模式在文本中出现的次数(文本中有多少不同的子字符串与该模式匹配)。文本仅由数字和拉丁字母组成。该模式可能包含以下特殊字符(这些字符不能出现在文本中):
“*”-正好对应一个任意字符;“%”-对应一个或两个数字(十进制数字系统中);“@”-对应一个拉丁字母。
下面我们来分析一些例子:
text: "te3t zdrte44q t33t"
pattern: "t\*%@"
字符串
说明:
模式“t*%@”可以匹配子字符串,如“te 3a”、“t337 q”等。* 正好对应一个任意字符,%对应一个或两个数字,@对应一个拉丁字母。
在给定的文本“te 3 t zdrte 44 q t33 t”中,该模式匹配三个子字符串:“te 3 t”、“te 44 q”和“t33 t”。
因此,此示例的预期输出为3。
text: "aaaaaa"
pattern: "aa"
Expected output: 5
型
....
text: "123"
pattern: "%%"
Expected output: 3
型
我在使用模式符号 * 和@方面取得了很大的进步。它们运行得很好,与预期的完全匹配一个字符。但是,我在使用%时遇到了一些障碍。与其他符号不同,它不仅可以匹配一个符号,有时还可以匹配两个符号,这让我有点头疼。
你看,棘手的是%没有固定的长度。它是可变的,所以它可以在一个示例中匹配一个符号,在另一个示例中匹配两个。弄清楚如何处理这种动态匹配对我来说现在有点挑战。
如果你有任何想法或建议如何解决这个问题,我真的很感激你的意见。
以下是我目前的代码:
#include <iostream>
using namespace std;
const int MAX_SIZE_TEXT = 201;
const int MAX_SIZE_PATTERN = 201;
unsigned getStrLen(char str[])
{
int i = 0, count = 0;
while (str[i] != '\0')
{
i++;
count++;
}
return count;
}
bool isLetter(char ch)
{
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
bool isDigit(char ch)
{
return ch >= '0' && ch <= '9';
}
unsigned countMatches(char text[], char pattern[])
{
int textLen = getStrLen(text);
int patternLen = getStrLen(pattern);
int i = 0, j = 0, currentLen = 0, matches = 0;
bool matchedASingleDigit = false;
while (i < textLen)
{
cout << text[i] << "?=" << pattern[j] << endl;
if (text[i] == pattern[j] || pattern[j] == '*'
|| (pattern[j] == '@' && isLetter(text[i])))
{
cout << "(before) i=" << i << "; j=" << j << endl;
currentLen += 1;
i++;
j++;
cout << "(after) i=" << i << "; j=" << j << endl;
cout << "currentLen = " << currentLen << endl;
if (currentLen == patternLen)
{
matches++;
}
}
else if (pattern[j] == '%')
{
/*if (isDigit(text[i]))
{
matchedASingleDigit = true;
currentLen += 1;
i++;
j++;
cout << "(after) i=" << i << "; j=" << j << endl;
cout << "currentLen = " << currentLen << endl;
if (currentLen == patternLen)
{
matches++;
}
}
if (i < textLen - 1 && isDigit[text])*/
}
else
{
i -= currentLen - 1;
j = 0;
cout << "(after) i=" << i << "; j=" << j << endl;
currentLen = 0;
cout << "currentLen = " << currentLen << endl;
}
}
return matches;
}
void testCountingMatches()
{
char text[MAX_SIZE_TEXT];
cin.getline(text, MAX_SIZE_TEXT);
char pattern[MAX_SIZE_PATTERN];
cin.getline(pattern, MAX_SIZE_PATTERN);
unsigned matches = countMatches(text, pattern);
cout << matches << endl;
}
int main()
{
testCountingMatches();
}
型
1条答案
按热度按时间eanckbw91#
对于初学者,您可以使用递归。
字符串
在这里我们首先将不同的
i
的计数分解成它自己的函数,然后我们可以利用递归来推进文本和模式指针。我已经尽可能地保持了代码与原始代码的接近。在分解后的函数中,我们只关心精确匹配,而在countMatches
函数中,我们枚举了所有可能的长度。尽管效率很低,这应该能够处理注解中的text: 3333, pattern: %3%
情况。正如@n.m.couldbeanAI评论的那样,让模式匹配变得高效并不容易。这并不意味着高效,只是为了给予你一个想法,因为你被卡住了。
演示:https://godbolt.org/z/PWjbhbjKK
代码的一些附加注解:
不要使用
using namespace std
。它现在看起来很方便,但迟早会起作用,请参阅this question以了解更多详细信息。在这种情况下,您需要从std
命名空间中获得的所有内容是cout
、cin
和endl
。因此,您应该拼写出std::cout
的全名,std::cin
和std::endl
(我的首选项),或者如果您不想在任何地方键入它们,请使用型
而不是.
另外,在这些地方实际上并不需要
std::endl
,应该只使用'\n'
,因为std::endl
会导致不必要的刷新。另外,不要写C风格的C++。C标准库已经提供了很多你可以使用的工具。如果你的老师是那些限制学生使用C标准库的人之一,那么他就没有真正正确地教C++,我对此感到遗憾。不管这是否是事实,你需要知道如何使用标准库。
比如说用
std::string
来代替固定长度的raw char数组,这样就不用担心MAX_SIZE_TEXT
够不够大了,不管你选择不选择raw char数组。除非有明确的要求,否则没有理由自己编写getStrLen
。如果您选择std::string
,则应使用std::string::size()
,或者std::strlen()
,如果你想坚持使用原始的char数组。也有std::isdigit()
,虽然那个更棘手,使用起来不会在程序中引入微妙的bug。