其实我是没有脸写这一篇文章的因为代码细节和后缀树知识点已经忘得一干二净了因为下面给出的代码已经尘封在硬盘里两年了我有一个不好的习惯那就是写代码过程比较考验脑力的话写完太累就不想补注释了,写注释一直拖下去直到今天也没写。我自己写的代码我已经看不懂了不知道为什么这样写suffixlink是什么也忘了想写一个后缀树教程也不可能了,如果代码有bug八成也没法修正了。下面仅贴出代码(没注释基本很难看懂,如果能从网上寻找资料学习看懂代码当我没说)#includeiostream#includemap#includestringusingnamespacestd;structExplicitNode;structBranchPoint{string rest;ExplicitNode*ptrnullptr;BranchPoint(conststringr,ExplicitNode*p):rest(r),ptr(p){}};structExplicitNode{boolisLeafNode;union{mapchar,BranchPointbranch_ptr;string suffix_str;};mapchar,BranchPoint::iterator parent_point_to_child_pos;ExplicitNode*suffix_linknullptr;ExplicitNode(conststrings):isLeafNode(true),suffix_str(s){}ExplicitNode():isLeafNode(false),branch_ptr(){}~ExplicitNode(){if(isLeafNode){suffix_str.~basic_string();}else{branch_ptr.~mapchar,BranchPoint();}}};pairExplicitNode*,ExplicitNode*constructSuffixTree(conststringinput){ExplicitNode*first_leafnullptr;ExplicitNode*rootnewExplicitNode();ExplicitNode*activation_noderoot;mapchar,BranchPoint::iterator it_for_act_node;intpre_node_scan_pos-1;string::size_type first_no_leaf_pos0;for(string::size_type i0;iinput.size();i){ExplicitNode*run_on_leaffirst_leaf;for(string::size_type k0;kfirst_no_leaf_pos;k){run_on_leaf-parent_point_to_child_pos-second.rest.append(1,input[i]);run_on_leaf-suffix_str.append(1,input[i]);if(k!first_no_leaf_pos-1)run_on_leafrun_on_leaf-suffix_link;}boolpre_stay_at_branchfalse;ExplicitNode*new_branch_node_extendnullptr;boolfinishfalse;string::size_type cur;for(string::size_type jfirst_no_leaf_pos;ji;j){if(pre_stay_at_branch){ExplicitNode*new_leafnewExplicitNode(input.substr(j,i-j1));auto_pairactivation_node-branch_ptr.insert(make_pair(input[i],BranchPoint(,new_leaf)));if(_pair.second){new_leaf-parent_point_to_child_pos_pair.first;run_on_leaf-suffix_linknew_leaf;run_on_leafnew_leaf;if(activation_node-suffix_link!nullptr){activation_nodeactivation_node-suffix_link;}else{first_no_leaf_posj1;pre_node_scan_pos-1;finishtrue;}}else{deletenew_leaf;it_for_act_node_pair.first;pre_node_scan_pos0;first_no_leaf_posj;finishtrue;}}else{ExplicitNode*runactivation_node;if(jfirst_no_leaf_pos){curi;}while(true){string::size_type k0;mapchar,BranchPoint::iterator it;if(run!root||pre_node_scan_pos-1){if(activation_node!rootpre_node_scan_pos!-1){kpre_node_scan_pos;itit_for_act_node;}else{itrun-branch_ptr.find(input[cur]);if(it!run-branch_ptr.end()){cur;}else{ExplicitNode*new_leafnewExplicitNode(input.substr(j,i-j1));new_leaf-parent_point_to_child_posrun-branch_ptr.insert(make_pair(input[cur],BranchPoint(,new_leaf))).first;if(run_on_leaf!nullptr){run_on_leaf-suffix_linknew_leaf;}else{first_leafnew_leaf;}run_on_leafnew_leaf;pre_stay_at_branchtrue;if(new_branch_node_extend!nullptr){new_branch_node_extend-suffix_linkrun;}if(run-suffix_link!nullptr){activation_noderun-suffix_link;}else{first_no_leaf_posj1;//ifinishtrue;}break;}}}else{kpre_node_scan_pos;itit_for_act_node;}for(;kit-second.rest.size()curi;k,cur){if(it-second.rest[k]!input[cur]){break;}}if(kit-second.rest.size()){if(curi){activation_nodeit-second.ptr;pre_node_scan_pos-1;first_no_leaf_posj;finishtrue;break;}else{runit-second.ptr;}}elseif(curi){activation_noderun;pre_node_scan_posk;first_no_leaf_posj;it_for_act_nodeit;finishtrue;break;}else{ExplicitNode*_newnewExplicitNode();it-second.ptr-parent_point_to_child_pos_new-branch_ptr.insert(make_pair(it-second.rest[k],BranchPoint(it-second.rest.substr(k1),it-second.ptr))).first;it-second.ptr_new;_new-parent_point_to_child_posit;if(new_branch_node_extend!nullptr){new_branch_node_extend-suffix_link_new;}new_branch_node_extend_new;it-second.rest.erase(k);ExplicitNode*new_leafnewExplicitNode(input.substr(j,i-j1));new_leaf-parent_point_to_child_pos_new-branch_ptr.insert(make_pair(input[cur],BranchPoint(,new_leaf))).first;run_on_leaf-suffix_linknew_leaf;run_on_leafnew_leaf;if(run-suffix_link!nullptr){activation_noderun-suffix_link;pre_node_scan_pos-1;cur(j1)i-j1-(k1)-1-1;}else{if(it-firstinput[j1]){it_for_act_nodeit;if(k!0){--k;}pre_node_scan_posk;}else{pre_node_scan_pos-1;curj1;}}break;}}}if(finish){break;}}}return{root,first_leaf};}voidprintSuffixTree(ExplicitNode*root,constintoffset,conststring::size_typestr_max_length,intlevel){if(root-isLeafNodefalse){cout||levelendl;for(mapchar,BranchPoint::iterator itroot-branch_ptr.begin();it!root-branch_ptr.end();it){for(inti1;ioffset;i){cout ;}cout it-firstit-second.rest;for(string::size_type i1;istr_max_length-it-second.rest.size()-1;i){cout ;}printSuffixTree(it-second.ptr,offset2str_max_length,str_max_length,level1);}}else{cout|-root-suffix_strendl;}}intmain(){//string _str ABABABC;string _strabcabxabcd;pairExplicitNode*,ExplicitNode*resultconstructSuffixTree(_str);ExplicitNode*rootresult.first;printSuffixTree(root,0,_str.size(),1);coutendl;cout叶节点中保存的全部后缀为:endl;for(ExplicitNode*_leafresult.second;_leaf!nullptr;_leaf_leaf-suffix_link){cout_leaf-suffix_strendl;}system(pause);return0;}