コンパイル原理の億点作業

#include
using namespace std;
const int maxn=1e2+5;
struct edge{
	char value;
	int to;
};
vector v[maxn<<2];
int id=0;
string s;
//-------------------------NFA---------------------------//
stack st,ed,str;
void print_nfa(){
	cout<"< dfav[maxn<<2];//dfa    
struct node{
	bool fg;//1      ，    
	set ns;//   
}; 
unordered_map mp;//dfa    ，     node   
bool vis[maxn<<2];
bool svis[maxn<<2];
set diff;//      
node bfs(set u,char c){ //     u       c    
	memset(vis,0,sizeof(vis));
	queue q;
	for(auto t:u){
		q.push(t);
	}
	set tv;
	bool bfg=0;
	while(!q.empty()){
		int tp=q.front();
		q.pop();
		for(auto it:v[tp]){
			if(it.value!=c) continue;
			else{
				if(vis[it.to]==1) continue;
				else {
					vis[it.to]=1;
					tv.insert(it.to);
                    if(c=='^') q.push(it.to); 
					if(it.to==1) bfg=1;//     
				}
			}
		}
	}
	return node{bfg,tv};
}

bool check(set x,set y){//          
	//0：   1：   
	if((int)x.size()!=(int)y.size()) return 1;
	set::iterator ix,iy;
	for(ix=x.begin(),iy=y.begin();ix!=x.end();++ix,++iy){
		if(*ix!=*iy) return 1;
	}
	return 0;
} 

node merge(node a,node b){//     
	node c;
	if(a.fg || b.fg)	c.fg=1;
	c.ns.insert(a.ns.begin(),a.ns.end());
	c.ns.insert(b.ns.begin(),b.ns.end());
	return c;
}

void print_set(set s){
	cout<"< nu;
	node nd;
	for(int i=0;i<=id;++i){
		for(auto it:v[i]){
			if(it.value!='^') diff.insert(it.value);
		}
	}
	nu.insert(0);
	nd=bfs(nu,'^');
	mp[0]=nd;
	queue q;
	q.push(0);
	nu.clear(),svis[0]=1;
	while(!q.empty()){
		int tp=q.front();
		q.pop();
		set tpset=mp[tp].ns; 
		for(char c:diff){//    c      
			node cnd=bfs(tpset,c);
			node knd=bfs(cnd.ns,'^');
			knd=merge(cnd,knd);
			if(!knd.ns.size()) continue; //  out 
			bool type=check(tpset,knd.ns);//knd.ns:      
			
			//          0:  ，1：   
			bool ffg=0; 
			for(auto it:mp){
				if(!check(it.second.ns,knd.ns)){//         
					dfav[tp].push_back({c,it.first});
					ffg=1;
					break; 
				}
			} 
			if(ffg) continue;
			//        
			mp[++did]=knd;
			dfav[tp].push_back({c,did});
			q.push(did); 
		}	
	}
	print_dfa();
}

//------------------------Min_DFA--------------------------//
vector miv[maxn<<2];
int fa[maxn<<2];
vector >setv;
unordered_map myhash;//    
int charnum; 
int matrix[maxn<<1][maxn<<1];//     
void init(){
	setv.clear();
	charnum=-1;
	for(char c:diff) myhash[c]=++charnum; //               
	for(int i=0;i<=did;++i){
		for(int j=0;j<=charnum;++j) matrix[i][j]=-1;
	}
	for(int i=0;i<=did;++i){
		for(auto it:dfav[i]){
			matrix[i][myhash[it.value]]=it.to;
		}
	}
}

int sec(int u){
	return u==fa[u]?u:fa[u]=sec(fa[u]); 
}

void unit(int x,int y){
	x=sec(x),y=sec(y);
	if(x==y) return;
	fa[y]=x;
}

void unitset(set s){//     
	for(auto i:s) fa[i]=i;
	set::iterator it;
	for(it=s.begin();it!=s.end();++it){
		if(it!=s.begin()){
			int a=*it,b=*(--it);
			++it;
			unit(a,b);
		} 
	}
} 

pair > > divide(set ns,char c){//  c      
	//1:      0   ,        
	set allfa;
	vector > res;
	bool fg=0;
	for(int i:ns){
		if(matrix[i][myhash[c]]==-1) allfa.insert(-1),fg=1;
		else allfa.insert(sec(i));
	}
	if(allfa.size()==1) return make_pair(1,res);
	if(fg){ //-1,   c，     
		set newset;
		for(int i:ns){
			if(matrix[i][myhash[c]]==-1) newset.insert(i);
		}
		res.push_back(newset);
	}
	for(auto nfa:allfa){
		if(nfa==-1) continue; 
		set newset;
		for(int i:ns){
			if(sec(matrix[i][myhash[c]])==nfa) newset.insert(i); 
		}
		res.push_back(newset);
	}
	for(auto nset:res) unitset(nset);//     ，       
	return make_pair(0,res);
}

pair > > check(set ns){//               
	//1:        0    ,         
	vector > res,run;
	if(ns.size()==1){//         
		return make_pair(1,res);
	}
	set::iterator it;
	run.push_back(ns);
	bool allflag=1;
	while( (int)run.size()!=0 ){//            
		bool fg=0;
		vector > tp;
		for(auto nset:run){
			bool nsetflag=1;
			for(char c:diff){
				pair > > p= divide(nset,c);
				if(p.first==0){
					allflag=0;
					nsetflag=0;
					tp.insert(tp.end(),p.second.begin(),p.second.end());
					break;
				}
			}
			if(nsetflag){//              
				res.push_back(nset); 
			}
		}
		run=tp;
	} 
	return make_pair(allflag,res);	
}

void min_dfa(){// dfav      
	//vector dfav[]      
	//map mp         
	init();//    
	set end_state,initial_state;
	for(auto it:mp){
		if(it.second.fg){//   
			end_state.insert(it.first);
		}
		else initial_state.insert(it.first);//   
	}
	unitset(initial_state);
	unitset(end_state);
	setv.push_back(end_state);
	setv.push_back(initial_state);
	while(1){
		bool flag=1; 
		vector > tp;
		for(auto nset:setv){
			pair > > np=check(nset);
			if(np.first==0) flag=0;
			tp.insert(tp.end(),np.second.begin(),np.second.end());
		}
		setv=tp;
		if(flag) break;//         
	}
	//   
	for(auto nset:setv){//          
		char rep=sec(*(nset.begin()));
		for(auto c:diff){
			if(matrix[rep][myhash[c]]==-1) continue;
			miv[rep].push_back({c,sec(matrix[rep][myhash[c]])});
		} 
	} 
}
int main(){
	cout<>s;
	nfa(); 
	dfa();
	min_dfa();
	return 0;
}

/* 
     ：a|b*
a|b* NFA ：
0--a->2
0--^->3
0--b->3
2--^->1
3--^->0
3--^->1
    ：
0    ，   ：0 1 3
1    ，   ：1 2
DFA ：
0--a->1
0--b->0
*/