搜索
代码清单：#includeiostream#includecstdio#includealgorithm#includecstring#includecctype#includevector#includestring#includequeue#includemap#includesstream#defineMAX507#defineDEBUGusingnamespacestd;classWF{public:stringleft,right;intback;intid;WF(chars1[],chars2[],intx,inty){left=s1;right=s2;back=x;id=y;}WF(conststring&s1,conststring&s2,intx,inty){left=s1;right=s2;back=x;id=y;}booloperator(constWF&a)const{if(left==a.left)returnrighta.right;returnlefta.left;}booloperator==(constWF&a)const{return(left==a.left)&&(right==a.right);}voidprint(){printf(%s-%s\n,left.c_str(),right.c_str());}};classClosure{public:vectorWFelement;voidprint(stringstr){printf(%-15s%-15s\n,,str.c_str());for(inti=0;ielement.size();i++)element[i].print();}booloperator==(constClosure&a)const{if(a.element.size()!=element.size())returnfalse;for(inti=0;ia.element.size();i++)if(element[i]==a.element[i])continue;elsereturnfalse;returntrue;}};structContent{inttype;intnum;stringout;Content(){type=-1;}Content(inta,intb):type(a),num(b){}};vectorWFwf;mapstring,vectorintdic;stringstart=S;vectorClosurecollection;vectorWFitems;charCH='$';intgo[MAX][MAX];intto[MAX];vectorcharV;boolused[MAX];Contentaction[MAX][MAX];intGoto[MAX][MAX];voidmake_item(){memset(to,-1,sizeof(-1));for(inti=0;iwf.size();i++)for(intj=0;j=wf[i].right.length();j++){stringtemp=wf[i].right;temp.insert(temp.begin()+j,CH);dic[wf[i].left].push_back(items.size());if(j)to[items.size()-1]=items.size();items.push_back(WF(wf[i].left,temp,i,items.size()));}#ifdefDEBUGputs(-------------------------项目表-------------------------);for(inti=0;iitems.size();i++)printf(%s-%s\n,items[i].left.c_str(),items[i].right.c_str());puts(--------------------------------------------------------);#endif}voidmake_set(){boolhas[MAX];for(inti=0;iitems.size();i++)if(items[i].left[0]=='S'&&items[i].right[0]==CH){Closuretemp;string&str=items[i].right;vectorWF&element=temp.element;element.push_back(items[i]);intx=0;for(x=0;xstr.length();x++)if(str[x]==CH)break;memset(has,0,sizeof(has));has[i]=1;if(x!=str.length()-1){queuestringq;q.push(str.substr(x+1,1));while(!q.empty()){stringu=q.front();q.pop();vectorint&id=dic[u];for(intj=0;jid.size();j++){inttx=id[j];if(items[tx].right[0]==CH){if(has[tx])continue;has[tx]=1;if(isupper(items[tx].right[1]))q.push(items[tx].right.substr(1,1));element.push_back(items[tx]);}}}}collection.push_back(temp);}for(inti=0;icollection.size();i++){mapint,Closuretemp;for(intj=0;jcollection[i].element.size();j++){stringstr=collection[i].element[j].right;intx=0;for(;xstr.length();x++)if(str[x]==CH)break;if(x==str.length()-1)continue;inty=str[x+1];intii;str.erase(str.begin()+x);str.insert(str.begin()+x+1,CH);WFcmp=WF(collection[i].element[j].left,str,-1,-1);for(intk=0;kitems.size();k++)if(items[k]==cmp){ii=k;break;}memset(has,0,sizeof(has));vectorWF&element=temp[y].element;element.push_back(items[ii]);has[ii]=1;x++;if(x!=str.length()-1){queuestringq;q.push(str.substr(x+1,1));while(!q.empty()){stringu=q.front();q.pop();vectorint&id=dic[u];for(intj=0;jid.size();j++){inttx=id[j];if(items[tx].right[0]==CH){if(has[tx])continue;has[tx]=1;if(isupper(items[tx].right[1]))q.push(items[tx].right.substr(1,1));element.push_back(items[tx]);}}}}}mapint,Closure::iteratorit=temp.begin();for(;it!=temp.end();it++)collection.push_back(it-second);for(inti=0;icollection.size();i++)sort(collection[i].element.begin(),collection[i].element.end());for(inti=0;icollection.size();i++)for(intj=i+1;jcollection.size();j++)if(collection[i]==collection[j])collection.erase(collection.begin()+j);}#ifdefDEBUGputs(-------------CLOSURE---------------------);stringstreamsin;for(inti=0;icollection.size();i++){sin.clear();stringout;sinclosure-Ii;sinout;collection[i].print(out);}puts();#endif}voidmake_V(){memset(used,0,sizeof(used));for(inti=0;iwf.size();i++){string&str=wf[i].left;for(intj=0;jstr.length();j++){if(used[str[j]])continue;used[str[j]]=1;V.push_back(str[j]);}string&str1=wf[i].right;for(intj=0;jstr1.length();j++){if(used[str1[j]])continue;used[str1[j]]=1;V.push_back(str1[j]);}}sort(V.begin(),V.end());V.push_back('#');}voidmake_cmp(vectorWF&cmp1,inti,charch){for(intj=0;jcollection[i].element.size();j++){stringstr=collection[i].element[j].right;intk;for(k=0;kstr.length();k++)if(str[k]==CH)break;if(k!=str.length()-1&&str[k+1]==ch){str.erase(str.begin()+k);str.insert(str.begin()+k+1,CH);cmp1.push_back(WF(collection[i].element[j].left,str,-1,-1));}}sort(cmp1.begin(),cmp1.end());}voidmake_go(){memset(go,-1,sizeof(go));intm=collection.size();for(intt=0;tV.size();t++){charch=V[t];for(inti=0;im;i++){vectorWFcmp1;make_cmp(cmp1,i,ch);coutcmp1.size()endl;if(cmp1.size()==0)continue;for(intj=0;jm;j++){vectorWFcmp2;for(intk=0;kcollection[j].element.size();k++){string&str=collection[j].element[k].right;intx;for(x=0;xstr.length();x++)if(str[x]==CH)break;if(x&&str[x-1]==ch)cmp2.push_back(WF(collection[j].element[k].left,str,-1,-1));}sort(cmp2.begin(),cmp2.end()