Overview
| SHA1 Hash: | a39d23ef9aade26e2d190ecdd9e079100ba2d645 |
|---|---|
| Date: | 2012-12-12 11:43:14 |
| User: | kinaba |
| Comment: | DFA minimization (initial prototype) |
| Timelines: | family | ancestors | descendants | both | trunk |
| Downloads: | Tarball | ZIP archive |
| Other Links: | files | file ages | manifest |
Tags And Properties
- branch=trunk inherited from [9165bd3629]
- sym-trunk inherited from [9165bd3629]
Changes
Added lib/graph/dfa_hopcroft.cpp version [7827709f822d3c66]
> 1 // TODO : optimize to O(n log n) > 2 // current version looks to be running in O(n^2) ... orz > 3 // > 4 // TODO : clean up as a library > 5 // > 6 // Copy&Paste from SRM562 Div1 Hard > 7 > 8 // Input is given as: > 9 // v----c---->G[v][c] > 10 // Must be a complete automaton. > 11 // !!! The following code is assuming |c|==4 !!! > 12 // > 13 // !!! The following code is assuming the final state is {0}. > 14 // > 15 mint solve(vector< vector<int> >& G) > 16 { > 17 vector< vector<int> > set_buffer; > 18 set<int> active_sets; > 19 set<int> active_splitters; > 20 > 21 { > 22 set_buffer.push_back( vector<int>(1,0) ); > 23 vector<int> all; > 24 for(int v=1; v<G.size(); ++v) > 25 all.push_back(v); > 26 set_buffer.push_back(all); > 27 > 28 active_sets.insert(0); > 29 active_sets.insert(1); > 30 active_splitters.insert(0); > 31 } > 32 > 33 while(!active_splitters.empty()) > 34 { > 35 const vector<int>& splv = set_buffer[*active_splitters.b > 36 set<int> spl(splv.begin(), splv.end()); > 37 active_splitters.erase(active_splitters.begin()); > 38 > 39 for(int d=0; d<4; ++d) > 40 for(set<int>::iterator it=active_sets.begin(); it!=activ > 41 { > 42 int ii = *it++; > 43 const vector<int>& cur = set_buffer[ii]; > 44 vector<int> t, f; > 45 for(int k=0; k<cur.size(); ++k) > 46 (spl.count(G[cur[k]][d]) ? t : f).push_b > 47 if(!t.empty() && !f.empty()) > 48 { > 49 set_buffer.push_back(t); > 50 set_buffer.push_back(f); > 51 active_sets.insert(set_buffer.size()-2); > 52 active_sets.insert(set_buffer.size()-1); > 53 if(active_splitters.count(ii)) { > 54 active_splitters.insert(set_buff > 55 active_splitters.insert(set_buff > 56 } else { > 57 active_splitters.insert(t.size() > 58 } > 59 active_splitters.erase(ii); > 60 active_sets.erase(ii); > 61 } > 62 } > 63 } > 64 > 65 vector<int> es; > 66 for(set<int>::iterator it=active_sets.begin(); it!=active_sets.e > 67 if(*it) > 68 es.push_back(set_buffer[*it].size()); > 69 /* > 70 for(bool changed=true; changed;) > 71 { > 72 changed=false; > 73 for(int i=0; i<eqs.size(); ++i) if(!eqs[i].second && !de > 74 set<int> spl(eqs[i].first.begin(), eqs[i].first. > 75 eqs[i].second = true; > 76 for(int k=0; k<eqs.size(); ++k) > 77 for(int d=0; d<4; ++d) if(!dead[k]) { > 78 vector<int> t, f; > 79 for(vector<int>::iterator it=eqs[k].firs > 80 (spl.count(G[*it][d]) ? t : f).p > 81 if(!t.empty() && !f.empty()) { > 82 if(eqs[k].second) { > 83 eqs.push_back(make_pair( > 84 eqs.push_back(make_pair( > 85 dead.push_back(false); > 86 dead.push_back(false); > 87 changed = true; > 88 } else { > 89 eqs.push_back(make_pair( > 90 eqs.push_back(make_pair( > 91 dead.push_back(false); > 92 dead.push_back(false); > 93 changed = true; > 94 } > 95 dead[k] = true; > 96 } > 97 } > 98 } > 99 } > 100 > 101 vector<int> es; > 102 for(int i=1; i<eqs.size(); ++i) if(!dead[i]) > 103 es.push_back(eqs[i].first.size()); > 104 */ > 105 int sum = accumulate(es.begin(), es.end(), 0); > 106 mint x = POW(2, sum); > 107 for(int i=0; i<es.size(); ++i) > 108 x -= POW(2, es[i])-1; > 109 return x-1; > 110 } > 111