128 lines
2.7 KiB
C++
128 lines
2.7 KiB
C++
#include <algorithm>
|
|
#include <array>
|
|
#include <cassert>
|
|
#include <iostream>
|
|
#include <list>
|
|
#include <map>
|
|
#include <regex>
|
|
#include <set>
|
|
#include <string>
|
|
#include <tuple>
|
|
|
|
struct Matcher
|
|
{
|
|
void add_rule(std::string const& s)
|
|
{
|
|
std::size_t len = 0;
|
|
unsigned long id = std::stoul(s, &len);
|
|
assert(s[len] == ':');
|
|
++len;
|
|
while (s[len] == ' ') {
|
|
++len;
|
|
}
|
|
if (rules_.size() <= id) {
|
|
rules_.resize(id + 1);
|
|
}
|
|
rules_[id] = s.substr(len);
|
|
}
|
|
|
|
void calculate_regex()
|
|
{
|
|
re42_ = expand_rule(42);
|
|
re31_ = expand_rule(31);
|
|
}
|
|
|
|
bool does_match(std::string const& s) const
|
|
{
|
|
std::smatch m;
|
|
std::string begin = "^" + re42_ + re42_;
|
|
unsigned repeats = 1;
|
|
while (std::regex_search(s, m, std::regex(begin))) {
|
|
std::string end = re31_ + "$";
|
|
std::string suffix = m.suffix();
|
|
for (unsigned i = 0; i < repeats; ++i) {
|
|
if (std::regex_search(suffix, std::regex("^" + end))) {
|
|
return true;
|
|
}
|
|
end = re31_ + end;
|
|
}
|
|
begin += re42_;
|
|
++repeats;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
private:
|
|
std::string expand_rule(std::size_t id)
|
|
{
|
|
std::string re;
|
|
std::string const& rule = rules_[id];
|
|
std::size_t pos = 0;
|
|
bool needs_brackets = false;
|
|
while (pos < rule.size()) {
|
|
if (rule[pos] == ' ') {
|
|
++pos;
|
|
}
|
|
else if (rule[pos] == '|') {
|
|
re += "|";
|
|
needs_brackets = true;
|
|
++pos;
|
|
}
|
|
else if (rule[pos] == '"') {
|
|
++pos;
|
|
while (pos < rule.size() && rule[pos] != '"') {
|
|
re += rule[pos];
|
|
++pos;
|
|
}
|
|
assert(pos < rule.size());
|
|
assert(rule[pos] == '"');
|
|
++pos;
|
|
}
|
|
else if (std::isdigit(rule[pos])) {
|
|
std::size_t len = 0;
|
|
std::size_t subid = std::stoul(rule.substr(pos), &len);
|
|
pos += len;
|
|
re += expand_rule(subid);
|
|
}
|
|
else {
|
|
assert(false);
|
|
}
|
|
}
|
|
|
|
if (needs_brackets) {
|
|
re = "(" + re + ")";
|
|
}
|
|
std::cout << "Rule " << id << " expands to: " << re << "\n";
|
|
return re;
|
|
}
|
|
|
|
std::vector<std::string> rules_;
|
|
std::string re42_;
|
|
std::string re31_;
|
|
};
|
|
|
|
int main(void)
|
|
{
|
|
std::string line;
|
|
Matcher matcher;
|
|
bool adding_rules = true;
|
|
unsigned matches = 0;
|
|
while (std::getline(std::cin, line)) {
|
|
if (line.empty()) {
|
|
adding_rules = false;
|
|
matcher.calculate_regex();
|
|
}
|
|
else if (adding_rules) {
|
|
matcher.add_rule(line);
|
|
}
|
|
else {
|
|
bool m = matcher.does_match(line);
|
|
std::cout << line << ": does " << (m ? "" : "not ") << "match\n";
|
|
matches += m;
|
|
}
|
|
}
|
|
|
|
std::cout << "Total number of matches: " << matches << "\n";
|
|
return 0;
|
|
} |