Cerinta completa
A regular expression is used to describe a set of strings. For this problem the alphabet is limited to ‘a’ and ‘b’.
We define to be a valid regular expression if:
1) is “” or ““.
2) is of the form ““, where and are regular expressions.
3) is of the form “” where and are regular expressions.
4) is of the form “” where is a regular expression.
Regular expressions can be nested and will always have have two elements in the parentheses. (‘‘ is an element, ‘‘ is not; basically, there will always be pairwise evaluation) Additionally, ‘‘ will always be the second element; ‘‘ is invalid.
The set of strings recognized by are as follows:
1) If is ““, then the set of strings recognized .
2) If is ““, then the set of strings recognized .
3) If is of the form “” then the set of strings recognized = all strings which can be obtained by a concatenation of strings and , where is recognized by and by .
4) If is of the form “” then the set of strings recognized = union of the set of strings recognized by and .
5) If is of the form “” then the the strings recognized are the empty string and the concatenation of an arbitrary number of copies of any string recognized by .
Task
Given a regular expression and an integer, , count how many strings of length are recognized by it.
Input Format
The first line contains the number of test cases . test cases follow.
Each test case contains a regular expression, , and an integer, .
Constraints
- It is guaranteed that will conform to the definition provided above.
Output Format
Print lines, one corresponding to each test case containing the required answer for the corresponding test case. As the answers can be very big, output them modulo .
Sample Input
3
((ab)|(ba)) 2
((a|b)*) 5
((a*)(b(a*))) 100
Sample Output
2
32
100
Explanation
For the first case, the only strings recognized are “” and ““. Of the possible strings of length , of them fit that expression.
For the second case, the RegEx recognizes any string of any length containing only ‘s and ‘s. The number of strings of length recognized by this expression is .
For the third case, the RegEx recognizes any string having one , preceeded and followed by any number of ‘s. There are strings of length which have a single in them.
Limbajul de programare folosit: cpp20
Cod:
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
/*
* Complete the 'countStrings' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. STRING r
* 2. INTEGER l
*/
static const int MOD = 1000000007;
static const int MAX_STATES = 256;
struct NFAState {
vector<int> eps;
array<vector<int>, 2> go;
};
struct Frag {
int s;
int t;
};
static string g_regex;
static int g_pos;
static vector<NFAState> g_nfa;
static int newState() {
g_nfa.push_back(NFAState());
return (int)g_nfa.size() - 1;
}
static Frag parseRegex();
static Frag literal(char c) {
int s = newState();
int t = newState();
g_nfa[s].go[c == 'a' ? 0 : 1].push_back(t);
return {s, t};
}
static Frag parseRegex() {
if (g_regex[g_pos] == 'a' || g_regex[g_pos] == 'b') {
char c = g_regex[g_pos++];
return literal(c);
}
// Form is one of: (R1R2), (R1|R2), (R1*)
++g_pos; // '('
Frag left = parseRegex();
if (g_regex[g_pos] == '*') {
++g_pos; // '*'
++g_pos; // ')'
int s = newState();
int t = newState();
g_nfa[s].eps.push_back(left.s);
g_nfa[s].eps.push_back(t);
g_nfa[left.t].eps.push_back(left.s);
g_nfa[left.t].eps.push_back(t);
return {s, t};
}
if (g_regex[g_pos] == '|') {
++g_pos; // '|'
Frag right = parseRegex();
++g_pos; // ')'
int s = newState();
int t = newState();
g_nfa[s].eps.push_back(left.s);
g_nfa[s].eps.push_back(right.s);
g_nfa[left.t].eps.push_back(t);
g_nfa[right.t].eps.push_back(t);
return {s, t};
}
// Concatenation (R1R2)
Frag right = parseRegex();
++g_pos; // ')'
g_nfa[left.t].eps.push_back(right.s);
return {left.s, right.t};
}
static vector<long long> mulVecMat(const vector<long long>& v, const vector<vector<long long>>& m) {
int n = (int)m.size();
vector<long long> res(n, 0);
for (int i = 0; i < n; ++i) {
if (v[i] == 0) continue;
long long vi = v[i];
for (int j = 0; j < n; ++j) {
if (m[i][j] == 0) continue;
res[j] = (res[j] + vi * m[i][j]) % MOD;
}
}
return res;
}
static vector<vector<long long>> mulMat(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {
int n = (int)a.size();
vector<vector<long long>> res(n, vector<long long>(n, 0));
for (int i = 0; i < n; ++i) {
for (int k = 0; k < n; ++k) {
if (a[i][k] == 0) continue;
long long aik = a[i][k];
for (int j = 0; j < n; ++j) {
if (b[k][j] == 0) continue;
res[i][j] = (res[i][j] + aik * b[k][j]) % MOD;
}
}
}
return res;
}
int countStrings(string r, int l) {
g_regex = r;
g_pos = 0;
g_nfa.clear();
Frag whole = parseRegex();
int n = (int)g_nfa.size();
if (n > MAX_STATES) return 0;
vector<bitset<MAX_STATES>> eclose(n);
for (int i = 0; i < n; ++i) {
vector<int> st;
st.push_back(i);
eclose[i].set(i);
while (!st.empty()) {
int u = st.back();
st.pop_back();
for (int v : g_nfa[u].eps) {
if (!eclose[i].test(v)) {
eclose[i].set(v);
st.push_back(v);
}
}
}
}
auto closureOf = [&](const bitset<MAX_STATES>& b) {
bitset<MAX_STATES> c;
for (int i = 0; i < n; ++i) {
if (b.test(i)) c |= eclose[i];
}
return c;
};
auto step = [&](const bitset<MAX_STATES>& b, int ch) {
bitset<MAX_STATES> moved;
for (int i = 0; i < n; ++i) {
if (!b.test(i)) continue;
for (int v : g_nfa[i].go[ch]) moved.set(v);
}
return closureOf(moved);
};
unordered_map<string, int> id;
vector<bitset<MAX_STATES>> dfaStates;
vector<array<int, 2>> trans;
vector<char> isAccept;
queue<int> q;
auto getId = [&](const bitset<MAX_STATES>& b) {
string key = b.to_string();
auto it = id.find(key);
if (it != id.end()) return it->second;
int idx = (int)dfaStates.size();
id.emplace(move(key), idx);
dfaStates.push_back(b);
trans.push_back({-1, -1});
isAccept.push_back(b.test(whole.t) ? 1 : 0);
q.push(idx);
return idx;
};
bitset<MAX_STATES> startBits;
startBits.set(whole.s);
startBits = closureOf(startBits);
int startId = getId(startBits);
while (!q.empty()) {
int cur = q.front();
q.pop();
bitset<MAX_STATES> toA = step(dfaStates[cur], 0);
bitset<MAX_STATES> toB = step(dfaStates[cur], 1);
trans[cur][0] = getId(toA);
trans[cur][1] = getId(toB);
}
int m = (int)dfaStates.size();
vector<vector<long long>> mat(m, vector<long long>(m, 0));
for (int i = 0; i < m; ++i) {
mat[i][trans[i][0]] = (mat[i][trans[i][0]] + 1) % MOD;
mat[i][trans[i][1]] = (mat[i][trans[i][1]] + 1) % MOD;
}
vector<long long> vec(m, 0);
vec[startId] = 1;
long long exp = l;
while (exp > 0) {
if (exp & 1LL) vec = mulVecMat(vec, mat);
exp >>= 1LL;
if (exp) mat = mulMat(mat, mat);
}
long long ans = 0;
for (int i = 0; i < m; ++i) {
if (isAccept[i]) {
ans += vec[i];
if (ans >= MOD) ans -= MOD;
}
}
return (int)ans;
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string t_temp;
getline(cin, t_temp);
int t = stoi(ltrim(rtrim(t_temp)));
for (int t_itr = 0; t_itr < t; t_itr++) {
string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);
vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));
string r = first_multiple_input[0];
int l = stoi(first_multiple_input[1]);
int result = countStrings(r, l);
fout << result << endl;
}
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
Scor obtinut: 1.0
Submission ID: 464635220
Link challenge: https://www.hackerrank.com/challenges/count-strings/problem