字符串解析-KMP魔改

本文主要是介绍字符串解析-KMP魔改，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

已知存在一种字符串解析语法，其中的语法元素如下
N:用于匹配单个数字(0-9)
A:用于匹配单个字母(a-z,A-Z)
n():用于表示一个分组，分组中至少有一个N语法元素或者A语法元素，n为一个数值，表示匹配n次，1<=n<= 200
输入给定的解析语法和字符串，要求从中找到第一个满足解析语法的字符串

输入

输入两行数据:
第一行是给定的解析语法
第二行是目标字符串
解析语法的长度n满足1<=n<= 100000
目标字符串长度n 满足 0<=n<= 100000

输出

输出匹配的字符串内容，如果没有匹配中任何字符串，输出!

样例1

输入：
2(AN)
BA3A3ABB
输出：
A3A3

样例2

输入：
2(A2(N))
A3322A33P20BB
输出:
A33P20

样例3

输入：
A5(N)
A3322A33P20BB
输出:
!

解法

先利用递归写出满足解析语法的一段字符串，任意字符串即可
然后把这个字符串和输入字符串进行kmp匹配，匹配时字符串相等修改为字母和字母相等，数字和数字相等

#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)using namespace std;
const int N = 1e4 + 10;
string synax, input, ans;
int idx;
map<int, int> mp;void parse(int l, int r) {for(int i = l; i <= r; i++) {if(synax[i] == 'A') {ans += 'a';} else if(synax[i] == 'N') {ans += '0';} else {string num;while(i < synax.size() && isdigit(synax[i])) {num += synax[i];i++;}int n = stoi(num), bk = mp[i];for(int j = 0; j < n; j++) {parse(i + 1, bk - 1);}i = bk;}}
}
bool isMatching(string str) {stack<int> s;for (int i = 0; i < str.size(); i++) {if (str[i] == '(') {s.push(i);} else if (str[i] == ')') {if (s.empty()) {return false;}mp[s.top()] = i;s.pop();}}if (!s.empty()) {return false;}return true;
}bool equal(char a, char b) {if((isdigit(a) && isdigit(b)) || (isalpha(a) && isalpha(b))) return true;return false;
}vector<int> Next(string pattern)
{vector<int> next;next.push_back(0);for (int i = 1, j = 0; i < pattern.length(); i++){while (j > 0 && pattern[j] != pattern[i]){ j = next[j - 1];}if (pattern[i] == pattern[j]){j++; }next.push_back(j);}return next;
}int main() {ios;cin >> synax >> input;isMatching(synax);parse(0, synax.size() - 1);vector<int>next = Next(ans);for (int i = 0, j = 0; i < input.length(); i++) {while (j > 0 && !equal(input[i], ans[j])) {j = next[j - 1];}if (equal(input[i], ans[j])) {j++;}if (j == ans.length()) {cout << input.substr(i - j + 1, ans.size()) << endl;return 0;j = next[j - 1];}}cout << "!";return 0;
}
/*
2(A2(N))
A3322A33P20BBa00a00A5(N)
A3322A33P20BB2(AN)
BA3A3ABB
*/