fork(2) download
copy 
  1. /* by Ashar Fuadi [fushar] */
  2.  
  3. #include <cstdio>
  4. #include <cstring>
  5.  
  6. #include <vector>
  7. #include <string>
  8. #include <stack>
  9. #include <queue>
  10. #include <map>
  11. #include <set>
  12. #include <iostream>
  13. #include <algorithm>
  14.  
  15. using namespace std;
  16.  
  17. #define REP(i,n) for (int i = 0; i < (int)n; i++)
  18. #define FOR(i, a, b) for (int i = (int)a; i <= (int)b; i++)
  19. #define RESET(c,v) memset(c, v, sizeof(c))
  20. #define REPE(i,c) for (typeof((c).end()) i = (c).begin(); i != (c).end(); ++i)
  21.  
  22.  
  23. typedef long long ll;
  24.  
  25. #define pb push_back
  26. #define mp make_pair
  27.  
  28.  
  29. struct NFA_node;
  30. struct DFA_node;
  31.  
  32. int NFA_ID;
  33. map<int, NFA_node*> NFA_map;
  34.  
  35. int DFA_ID;
  36. map<set<int>, DFA_node*> DFA_map;
  37.  
  38. struct DFA_node
  39. {
  40. 	DFA_node* next[2];
  41. 	set<int> states;
  42. 	int id;
  43.  
  44. 	DFA_node()
  45. 	{
  46. 		next[0] = next[1] = NULL;
  47. 		id = DFA_ID++;
  48. 	}
  49.  
  50. 	static DFA_node* create(set<int> states)
  51. 	{
  52. 		if (DFA_map.count(states))
  53. 			return DFA_map[states];
  54. 		DFA_node* o = new DFA_node();
  55. 		o->states = states;
  56. 		DFA_map[states] = o;
  57. 		return o;
  58. 	}
  59.  
  60. 	~DFA_node()
  61. 	{
  62. 		REP(i, 2) if (next[i])
  63. 			delete next[i];
  64. 	}
  65. };
  66.  
  67.  
  68. struct NFA_node
  69. {
  70. 	vector<NFA_node*> next[3];
  71. 	int id;
  72.  
  73. 	NFA_node()
  74. 	{
  75. 		NFA_map[NFA_ID] = this;
  76. 		id = NFA_ID++;
  77. 	}
  78.  
  79. 	~NFA_node()
  80. 	{
  81. 		REP(i, 3) REP(j, next[i].size()) if (next[i][j])
  82. 			delete next[i][j];
  83. 	}
  84. };
  85.  
  86. struct NFA_state
  87. {
  88. 	NFA_node* start;
  89. 	NFA_node* end;
  90.  
  91. 	NFA_state(NFA_node* st, NFA_node* ed)
  92. 	{
  93. 		start = st;
  94. 		end = ed;
  95. 	}
  96. };
  97.  
  98. int N, L;
  99. string regex;
  100.  
  101. set<int> eps_closure(set<int> states)
  102. {
  103. 	stack<int> st;
  104. 	for (set<int>::iterator i = states.begin(); i != states.end(); ++i)
  105. 		st.push(*i);
  106. 	set<int> res = states;
  107. 	while (!st.empty())
  108. 	{
  109. 		int t = st.top(); st.pop();
  110.  
  111. 		NFA_node* u = NFA_map[t];
  112.  
  113. 		REP(i, u->next[2].size())
  114. 		{
  115. 			NFA_node* v = u->next[2][i];
  116. 			if (!res.count(v->id))
  117. 			{
  118. 				res.insert(v->id);
  119. 				st.push(v->id);
  120. 			}
  121. 		}
  122. 	}
  123. 	return res;
  124. }
  125.  
  126. set<int> move_closure(set<int> states, int c)
  127. {
  128. 	queue<pair<int, bool> > st;
  129. 	for (set<int>::iterator i = states.begin(); i != states.end(); ++i)
  130. 		st.push(make_pair(*i, false));
  131. 	set<int> res;
  132. 	set<pair<int, bool> > used;
  133. 	for (set<int>::iterator i = states.begin(); i != states.end(); ++i)
  134. 		used.insert(make_pair(*i, false));
  135.  
  136. 	while (!st.empty())
  137. 	{
  138. 		int t = st.front().first;
  139. 		bool r = st.front().second;
  140. 		st.pop();
  141. 		NFA_node* u = NFA_map[t];
  142. 		REP(i, u->next[2].size())
  143. 		{
  144. 			NFA_node* v = u->next[2][i];
  145. 			if (!used.count(make_pair(v->id, r)))
  146. 			{
  147. 				used.insert(make_pair(v->id, r));
  148. 				st.push(make_pair(v->id, r));
  149. 				if (r)
  150. 				{
  151. 					res.insert(v->id);
  152. 				}
  153. 			}
  154. 		}
  155. 		if (r) continue;
  156. 		REP(i, u->next[c].size())
  157. 		{
  158. 			NFA_node* v = u->next[c][i];
  159. 			if (!used.count(make_pair(v->id, true)))
  160. 			{
  161. 				used.insert(make_pair(v->id, true));
  162. 				st.push(make_pair(v->id, true));
  163. 				res.insert(v->id);
  164. 			}
  165. 		}
  166. 	}
  167. 	return res;
  168. }
  169.  
  170. int K;
  171. typedef vector<vector<ll> > mat;
  172. const ll MOD = 1000000007;
  173.  
  174. mat mul(mat a, mat b)
  175. {
  176. 	mat c = mat(K, vector<ll>(K));
  177. 	REP(i, K) REP(j, K) REP(k, K)
  178. 	{
  179. 		c[i][j] += (a[i][k] * b[k][j]) % MOD;
  180. 		c[i][j] %= MOD;
  181. 	}
  182. 	return c;
  183. }
  184.  
  185. mat pow(mat a, int p)
  186. {
  187. 	if (p == 1)
  188. 		return a;
  189. 	if (p % 2)
  190. 		return mul(a, pow(a, p-1));
  191. 	mat x = pow(a, p/2);
  192. 	return mul(x, x);
  193. }
  194.  
  195. int main()
  196. {
  197. 	cin >> N;
  198. 	REP(n, N)
  199. 	{
  200. 		NFA_ID = 0;
  201. 		NFA_map.clear();
  202. 		DFA_ID = 0;
  203. 		DFA_map.clear();
  204. 		regex = "";
  205. 		string s;
  206. 		cin >> s >> L;
  207.  
  208. 		// insert concatenation operators
  209. 		REP(i, s.size())
  210. 		{
  211. 			if (i && (s[i] == '(' || s[i] == 'a' || s[i] == 'b') &&
  212. 				     (s[i-1] == ')' || s[i-1] == 'a' || s[i-1] == 'b'))
  213. 				regex += "^";
  214. 			regex += s[i];
  215. 		}
  216.  
  217. 		stack<char> ops;
  218. 		stack<NFA_state*> states;
  219. 		int irvan = 0, kurung = 0;
  220. 		REP(i, regex.size())
  221. 		{
  222. 			if (regex[i] == '(')
  223. 				continue;
  224. 			else if (regex[i] == 'a' || regex[i] == 'b')
  225. 			{
  226. 				NFA_node* st = new NFA_node();
  227. 				NFA_node* ed = new NFA_node();
  228. 				st->next[regex[i]-'a'].push_back(ed);
  229. 				NFA_state* state = new NFA_state(st, ed);
  230.  
  231. 				states.push(state);
  232. 			}
  233. 			else if (regex[i] == ')')
  234. 			{
  235. 				char op = ops.top();
  236. 				ops.pop();
  237. 				if (op == '^')
  238. 				{
  239. 					NFA_state* b = states.top(); states.pop();
  240. 					NFA_state* a = states.top(); states.pop();
  241. 					a->end->next[2].push_back(b->start);
  242. 					NFA_state* state = new NFA_state(a->start, b->end);
  243. 					states.push(state);
  244. 				}
  245. 				else if (op == '|')
  246. 				{
  247. 					NFA_state* b = states.top(); states.pop();
  248. 					NFA_state* a = states.top(); states.pop();
  249. 					NFA_node* start = new NFA_node();
  250. 					NFA_node* end = new NFA_node();
  251. 					start->next[2].push_back(a->start);
  252. 					start->next[2].push_back(b->start);
  253. 					a->end->next[2].push_back(end);
  254. 					b->end->next[2].push_back(end);
  255. 					NFA_state* state = new NFA_state(start, end);
  256. 					states.push(state);
  257. 				}
  258. 				else if (op == '*')
  259. 				{
  260. 					NFA_state* a = states.top(); states.pop();
  261. 					NFA_node* start = new NFA_node();
  262. 					NFA_node* end = new NFA_node();
  263. 					start->next[2].push_back(a->start);
  264. 					start->next[2].push_back(end);
  265. 					a->end->next[2].push_back(a->start);
  266. 					a->end->next[2].push_back(end);
  267. 					NFA_state* state = new NFA_state(start, end);
  268. 					states.push(state);
  269. 				}
  270. 			}
  271. 			else
  272. 				ops.push(regex[i]);
  273. 		}
  274.  
  275. 		NFA_node* NFA_start = states.top()->start;
  276. 		NFA_node* NFA_end = states.top()->end;
  277. 		states.pop();
  278.  
  279. 		set<int> start_set;
  280. 		set<int> used;
  281.  
  282. 		start_set.insert(NFA_start->id);
  283.  
  284. 		start_set = eps_closure(start_set);
  285.  
  286. 		DFA_node* DFA_start = DFA_node::create(start_set);
  287. 		used.insert(DFA_start->id);
  288.  
  289. 		queue<DFA_node*> q;
  290. 		q.push(DFA_start);
  291.  
  292. 		while (!q.empty())
  293. 		{
  294. 			DFA_node* u = q.front(); q.pop();
  295.  
  296. 			REP(c, 2)
  297. 			{
  298. 				set<int> lho = move_closure(u->states, c);
  299. 				if (lho.empty()) continue;
  300. 				DFA_node* v = DFA_node::create(lho);
  301. 				u->next[c] = v;
  302. 				if (!used.count(v->id))
  303. 				{
  304. 					used.insert(v->id);
  305. 					q.push(v);
  306. 				}
  307. 			}
  308. 		}
  309.  
  310.  
  311. 		REPE(i, DFA_map)
  312. 			i->second->trace(NFA_end->id);
  313.  
  314. 		REPE(i, NFA_map)
  315. 			i->second->trace();
  316.  
  317.  
  318. 		K = DFA_ID;
  319. 		mat R(K, vector<ll>(K));
  320. 		for (map<set<int>, DFA_node*>::iterator i = DFA_map.begin(); i != DFA_map.end(); ++i)	
  321. 		{
  322. 			DFA_node* u = i->second;
  323. 			REP(c, 2)
  324. 			{
  325. 				DFA_node* v = u->next[c];
  326. 				if (v)
  327. 				{
  328. 					R[v->id][u->id]++;
  329. 				}
  330. 			}
  331. 		}
  332.  
  333. 		R = pow(R, L);
  334. 		ll res = 0;
  335. 		for (map<set<int>, DFA_node*>::iterator i = DFA_map.begin(); i != DFA_map.end(); ++i)
  336. 			if (i->second->states.count(NFA_end->id))
  337. 			res = (res + R[i->second->id][0]) % MOD;
  338.  
  339. 		printf("%lld\n", res);
  340. 	}
  341. }
  342.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/1Fqxw
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!