題目

已知存在一種字符串解析語法，其中的語法元素如下
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
*/