#include<array>#include<iostream>#include<unordered_map>#include<vector>constexprintL=3;std::array<int,1<<L>op;constexprintX=(1<<L)-2;// Build a DFA that accepts binary strings which evaluate to a given string.// 0b000 → "00"// 0b001 → "01"// 0b010 → "10"// 0b011 → "11"// 0b100 → "0"// 0b101 → "1"DFAbuild(intx){constexprintL1=9,L2=6;// The result for string `st` of length `len` is stored at (1 << len) | st.constautoidx=[](intlen,intst)->int{return(1<<len)|st;};// Compute which bit strings are accepted using dynamic programming.std::vector<bool>acc(1<<(L1+L2+1));acc[(x>>2)?idx(1,x&1):idx(2,x)]=true;for(intlen=(x>>2)?3:4;len<=L1+L2;len+=2){for(intst=0;st<(1<<len);++st){for(inti=0;i+L<=len;++i){// Replace st[i..i+2] using the op[] rule, and check if the result is// accepted. Result = st[0..i-1] + op[st[i..i+2]] + st[i+3..end]intpr=((((st>>(i+L))<<1)|op[(st>>i)&((1<<L)-1)])<<i)|(st&((1<<i)-1));if(acc[idx(len-2,pr)]){acc[idx(len,st)]=true;break;}}}}// Construct a DFA using the Myhill-Nerode theorem.DFAdfa(2);std::unordered_map<std::vector<bool>,int>mp;// Maps characteristic vectors to state IDs.std::vector<int>sts;// Representative 01 strings for each state.std::vector<int>ids(1<<(L1+1));// Maps 01 strings to DFA state IDs.for(intlen=0;len<=L1;++len){for(intst=(1<<len);st<(2<<len);++st){// Construct characteristic vector for this prefix.std::vector<bool>key(1<<(L2+1));for(intnxt=0;nxt<=L2;++nxt)std::copy(acc.begin()+(st<<nxt),acc.begin()+((st+1)<<nxt),key.begin()+(1<<nxt));if(!mp.count(key)){mp[key]=dfa.n++;sts.push_back(st);dfa.acc.push_back(key[idx(0,0)]);}ids[st]=mp[key];}}// Build transitions.for(intc=0;c<2;++c){dfa.trans[c].resize(dfa.n);for(inti=0;i<dfa.n;++i)dfa.trans[c][i]=ids[(sts[i]<<1)|c];}returndfa;}std::vector<DFA>dfa;// Initialize the DFA's.voidinit(){std::strings;std::cin>>s;for(inti=0;i<(1<<L);++i)op[i]=s[i]-'0';std::swap(op[1],op[4]);std::swap(op[3],op[6]);for(intx=0;x<X;++x)dfa.push_back(build(x));}std::strings;constexprintB=5;// Block size is 2^B.std::vector<std::vector<std::array<std::vector<int>,X>>>pre;voidprecompute(){intn=s.size();for(inti=0;i<n;++i)s[i]-='0';intnn=((n-1)>>B)+1;pre.clear();// Compute transitions over single blocks (2^B characters) for each DFA.pre.emplace_back(nn);for(inti=0;i<nn;++i){for(intx=0;x<X;++x){pre[0][i][x].resize(dfa[x].n);for(intj=0;j<dfa[x].n;++j){intcr=j;for(intii=(i<<B);ii<((i+1)<<B)&&ii<n;++ii)cr=dfa[x].trans[s[ii]][cr];pre[0][i][x][j]=cr;}}}// Build higher-level transitions using binary lifting.for(intd=1;(1<<d)<=nn;++d){pre.emplace_back(nn-(1<<d)+1);for(inti=0;i<=nn-(1<<d);++i){for(intx=0;x<X;++x){pre[d][i][x].resize(dfa[x].n);for(intj=0;j<dfa[x].n;++j)pre[d][i][x][j]=pre[d-1][i+(1<<(d-1))][x][pre[d-1][i][x][j]];}}}}// Check if the x-th DFA accepts s[l...r].boolcheck(intl,intr,intx){if(l>r)returnfalse;intcr=dfa[x].q0;if((l>>B)==(r>>B)){for(;l<=r;++l)cr=dfa[x].trans[s[l]][cr];}else{for(;(l&((1<<B)-1))&&(l<=r);++l)cr=dfa[x].trans[s[l]][cr];intd=(r>>B)-(l>>B);for(intz=0;z<(int)pre.size();++z)if((d>>z)&1){cr=pre[z][l>>B][x][cr];l+=1<<(z+B);}for(;l<=r;++l)cr=dfa[x].trans[s[l]][cr];}returndfa[x].acc[cr];}// Construct expression for s[l...r].voidcalc(intl,intr,intx){if(l==r)return(void)(std::cout<<(x&1));if(x>>2){for(inti=l,j=r;i<=j;i+=2,j-=2){for(intk=0;k<(1<<L);++k){if(op[k]!=(x&1))continue;if(check(l,i,(k>>2)|4)&&check(i+1,r,k&3)){std::cout<<'(';calc(l,i,(k>>2)|4);calc(i+1,r,k&3);std::cout<<')';return;}if(check(l,j-1,k>>1)&&check(j,r,(k&1)|4)){std::cout<<'(';calc(l,j-1,k>>1);calc(j,r,(k&1)|4);std::cout<<')';return;}}}}else{for(inti=l,j=r;i<=j;i+=2,j-=2){if(check(l,i,(x>>1)|4)&&(check(i+1,r,(x&1)|4))){calc(l,i,(x>>1)|4);calc(i+1,r,(x&1)|4);return;}if(check(l,j-1,(x>>1)|4)&&check(j,r,(x&1)|4)){calc(l,j-1,(x>>1)|4);calc(j,r,(x&1)|4);return;}}}}voidsolve(){std::cin>>s;intn=s.size();precompute();if(!check(0,n-1,0b101)){std::cout<<-1<<'\n';return;}calc(0,n-1,0b101);std::cout<<'\n';}intmain(){init();intq;std::cin>>q;for(;q;--q){solve();}return0;}
// DFA minimization via Hopcroft's algorithm.// Complexity: O(n * m * log(n)).DFADFA::hopcroft_minimize()const{// Construct inverse transition maps:// - pre[c] stores states sorted by the target of transition c.// - pos[c][s] is the start index in pre[c] of transitions going to state s.std::vector<std::vector<int>>pre(m),pos(m);for(intc=0;c<m;++c){pre[c].assign(n,0);pos[c].assign(n+1,0);// Counting sort.for(inti=0;i<n;++i)++pos[c][trans[c][i]];for(inti=0;i<n;++i)pos[c][i+1]+=pos[c][i];for(inti=0;i<n;++i)pre[c][--pos[c][trans[c][i]]]=i;}// Partition element structure:// - os: starting index in the state list.// - sz: number of states in this class.// - cnt: temporary count of marked states during refinement.structEquivClasses{intos,sz,cnt;EquivClasses(intos,intsz,intcnt):os(os),sz(sz),cnt(cnt){}};// Partition and helper data structures.std::vector<EquivClasses>ec;// Current list of equivalence classes.std::vector<int>ids(n);// Permutation of states, grouped by ECs.std::vector<int>par(n);// Maps state to its EC index.std::vector<bool>tag(n);// Temporary marking for splitting.std::queue<int>evidences;// Worklist of ECs to check.// Initial partition by acceptance label.std::iota(ids.begin(),ids.end(),0);std::sort(ids.begin(),ids.end(),[&](intl,intr){returnacc[l]<acc[r];});for(intl=0,r;l<n;l=r){for(r=l;r<n&&acc[ids[r]]==acc[ids[l]];++r)par[ids[r]]=ec.size();if(l)evidences.push(ec.size());// Add all but first class to worklist.ec.emplace_back(l,r-l,0);}// Refinement loop.while(!evidences.empty()){intcr=evidences.front();evidences.pop();for(intc=0;c<m;++c){std::vector<int>todo;for(inti=ec[cr].os;i<ec[cr].os+ec[cr].sz;++i){for(intk=pos[c][ids[i]];k<pos[c][ids[i]+1];++k){intj=pre[c][k];if(!tag[j]){if(!ec[par[j]].cnt)todo.push_back(par[j]);++ec[par[j]].cnt;tag[j]=true;}}}// Perform splits.for(inti:todo){intti=i;if(ec[i].cnt!=ec[i].sz){// Split into two: larger vs smaller segment.boolmajority_tagged=ec[i].cnt*2>=ec[i].sz;intmid=std::partition(ids.begin()+ec[i].os,ids.begin()+ec[i].os+ec[i].sz,[&](intx){returntag[x]==majority_tagged;})-ids.begin()-ec[i].os;// Assign new EC index to the smaller segment.for(intj=ec[i].os+mid;j<ec[i].os+ec[i].sz;++j)par[ids[j]]=ec.size();evidences.push(ec.size());if(!majority_tagged)ti=ec.size();ec.emplace_back(ec[i].os+mid,ec[i].sz-mid,0);ec[i].sz=mid;}// Clear temporary counters and tags.ec[i].cnt=0;for(intj=ec[ti].os;j<ec[ti].os+ec[ti].sz;++j)tag[ids[j]]=false;}}}// Build minimized DFA.DFAres(m,ec.size(),par[q0]);for(constauto&e:ec){inti=ids[e.os];// Representative state.res.acc[par[i]]=acc[i];for(intc=0;c<m;++c)res.trans[c][par[i]]=par[trans[c][i]];}returnres;}
这一参考实现允许自动机的状态带有任何整数取值的标签,而并非简单的「接受」与「不接受」的二元标签。从参考实现可以看出,与基础 Hopcroft 算法的唯一不同就在于初始划分和证据集合的构造。这种拓展的自动机也称为 Moore 机。它的一个应用可以看本节的第二个例题。
#include<bitset>#include<cmath>#include<iostream>#include<unordered_map>#include<vector>constexprintB=10,L=91;usingstate=std::bitset<L>;DFAraw_dfa(B),dfa(B);std::unordered_map<state,int>ids;// Construct a DFA by DFS.intdfs(conststate&cr){if(ids.count(cr))returnids[cr];intid=ids[cr]=raw_dfa.n++;// Check if accepted.for(inti=0;i<B;++i){if(cr[i]){raw_dfa.acc.push_back(i);break;}}// Construct transitions recursively.for(intc=0;c<B;++c){raw_dfa.trans[c].push_back(0);}for(intc=0;c<B;++c){statent;for(inti=0;i<L;++i){if(cr[i]){if(i+c<L)nt[i+c]=true;nt[std::abs(i-c)]=true;}}raw_dfa.trans[c][id]=dfs(nt);}returnid;};// DP.std::vector<longlong>memo;std::vector<int>nums;longlongsol(intx,intlen,boollim,intk){if(!len)returndfa.acc[x]<=k;autokey=(x*20+len)*B+k;if(!lim&&memo[key]!=-1)returnmemo[key];longlongres=0;for(intc=0;c<=(lim?nums[len-1]:B-1);++c)res+=sol(dfa.trans[c][x],len-1,lim&&c==nums[len-1],k);returnlim?res:memo[key]=res;};longlongcalc(longlongn,intk){nums.clear();for(;n;n/=B)nums.push_back(n%B);returnsol(dfa.q0,nums.size(),true,k);};intmain(){// Construct a DFA.for(intc=0;c<B;++c)raw_dfa.trans[c].reserve(20000);dfs(1);// DFA minimization.dfa=raw_dfa.hopcroft_minimize();memo.assign(dfa.n*20*B,-1);// Queries.intt;std::cin>>t;for(;t;--t){longlongl,r;intk;std::cin>>l>>r>>k;std::cout<<(calc(r,k)-calc(l-1,k))<<'\n';}return0;}
Knuutila, Timo. "Re-describing an algorithm by Hopcroft." Theoretical Computer Science 250, no. 1-2 (2001): 333-363.
Hopcroft, John E., Rajeev Motwani, and Jeffrey D. Ullman. "Introduction to automata theory, languages, and computation." Acm Sigact News 32, no. 1 (2001): 60-65.