DC3是一个能在线性时间内计算后缀数组的有效算法该算法的详解请参看数据结构与算法分析(java语言描述 Mark Allen Weiss著)12.4.3节,这里就不重复讲解了具体的C实现代码是(测试难度大可能存在bug因此仅供参考):#includeiostream#includestring#includevector#includerandom#includectime#includesetusingnamespacestd;//字符串只能由小写英文字母组成voidradixSort(vectorstring::size_typerank_info,vectorstring::size_typeresult,size_t radix_value,size_t offset,vectorstring::size_typesort_pos){vectorintbucket(radix_value,0);for(vectorchar::size_type i0;isort_pos.size();i){if(sort_pos[i]offsetrank_info.size()){bucket[0];}else{bucket[rank_info[sort_pos[i]offset]];}}for(vectorchar::size_type i1;ibucket.size();i){bucket[i]bucket[i-1]bucket[i];}if(sort_pos.size()!0){for(vectorstring::size_type::size_type isort_pos.size()-1;;--i){if(sort_pos[i]offsetrank_info.size()){result[--bucket[0]]sort_pos[i];}else{result[--bucket[rank_info[sort_pos[i]offset]]]sort_pos[i];}if(i0){break;}}}}boolcompareChar(vectorstring::size_typerank_info,string::size_type i,string::size_type j){if(irank_info.size()){if(jrank_info.size()){returntrue;}elseif(rank_info[j]0){returntrue;}}else{if(jrank_info.size()){if(rank_info[i]0){returntrue;}}else{if(rank_info[i]rank_info[j]){returntrue;}}}returnfalse;}boolposIsZero(vectorstring::size_typerank_info,string::size_type i){if(irank_info.size()){returntrue;}if(rank_info[i]0){returntrue;}returnfalse;}boolallIsZero(vectorstring::size_typerank_info,size_t i,vectorstring::size_typeresult){returnposIsZero(rank_info,result[i])posIsZero(rank_info,result[i]1)posIsZero(rank_info,result[i]2);}booltailHasZero(vectorstring::size_typerank_info,size_t i,vectorstring::size_typeresult){returnposIsZero(rank_info,result[i])||posIsZero(rank_info,result[i]1)||posIsZero(rank_info,result[i]2);}boolcompareFirstThree(vectorstring::size_typerank_info,size_t i,size_t j,vectorstring::size_typeresult){returncompareChar(rank_info,result[i],result[j])compareChar(rank_info,1result[i],1result[j])compareChar(rank_info,2result[i],2result[j]);}size_tgetRank(vectorstring::size_typerank_info,size_t pos){if(posrank_info.size()){return0;}else{returnrank_info[pos];}}voidDC3(vectorstring::size_typerank_info,vectorstring::size_typeSA,size_t radix_value){size_t rest;size_t original_tailrank_info.size();if((restrank_info.size()%3)!0){for(size_t i1;i3-rest;i)rank_info.push_back(0);}vectorstring::size_typesuffix_pos_be_sorted;intr0;for(string::size_type i0;irank_info.size();i){if(r1||r2){suffix_pos_be_sorted.push_back(i);}r;if(r3)r0;}vectorstring::size_typeresult(suffix_pos_be_sorted.size());radixSort(rank_info,result,radix_value,2,suffix_pos_be_sorted);radixSort(rank_info,suffix_pos_be_sorted,radix_value,1,result);radixSort(rank_info,result,radix_value,0,suffix_pos_be_sorted);intcount0;boolhas_found_equalfalse;boolhas_pass_inequal_regionfalse;vectorstring::size_typemod3_rank(rank_info.size());size_t rank_value1;for(vectorstring::size_type::size_type i1;iresult.size();i){if(compareFirstThree(rank_info,i-1,i,result)){if(allIsZero(rank_info,i-1,result)){mod3_rank[result[i-1]]0;count;}else{mod3_rank[result[i-1]]rank_value;}if(has_found_equalfalse){has_found_equaltrue;if(has_pass_inequal_region){has_pass_inequal_regionfalse;--count;}else{if(i!1)--count;}}}else{if(allIsZero(rank_info,i-1,result)){mod3_rank[result[i-1]]0;count;}else{mod3_rank[result[i-1]]rank_value;rank_value;}if(has_found_equal){has_found_equalfalse;}else{has_pass_inequal_regiontrue;if(i1){if(!allIsZero(rank_info,i-1,result))count;}}count;}}if(allIsZero(rank_info,result.size()-1,result)){mod3_rank[result.back()]0;count;}else{mod3_rank[result.back()]rank_value;}if(count!result.size()){vectorstring::size_typenew_str_after_joint;for(string::size_type i0;irank_info.size();i){if(i%31){new_str_after_joint.push_back(mod3_rank[i]);}}for(string::size_type i0;irank_info.size();i){if(i%32){new_str_after_joint.push_back(mod3_rank[i]);}}vectorstring::size_typeSA2(new_str_after_joint.size());DC3(new_str_after_joint,SA2,rank_value1);size_t k0;for(size_t i0;iSA2.size();i){if(SA2[i](rank_info.size()-2)/3){result[i]3*SA2[i]1;}else{result[i]3*(SA2[i]-(rank_info.size()-2)/3-1)2;}}}vectorstring::size_typemod3_equal_zero_sort;for(vectorstring::size_type::size_type i0;iresult.size();i){if(result[i]%31){mod3_equal_zero_sort.push_back(result[i]-1);}}vectorstring::size_typemod3_equal_zero_sort_result(mod3_equal_zero_sort.size());radixSort(rank_info,mod3_equal_zero_sort_result,radix_value,0,mod3_equal_zero_sort);vectorstring::size_typerank(rank_info.size());for(size_t i0;iresult.size();i){rank[result[i]]i1;}rank.push_back(0);rank.push_back(0);size_t t0;size_t i0,j0;vectorsize_tmerge_result(rank_info.size());for(;imod3_equal_zero_sort_result.size()jresult.size();){if(getRank(rank_info,mod3_equal_zero_sort_result[i])getRank(rank_info,result[j])){merge_result[t]mod3_equal_zero_sort_result[i];i;}elseif(getRank(rank_info,mod3_equal_zero_sort_result[i])getRank(rank_info,result[j])){merge_result[t]result[j];j;}else{if(result[j]%31){if(rank[mod3_equal_zero_sort_result[i]1]rank[result[j]1]){merge_result[t]mod3_equal_zero_sort_result[i];i;}else{merge_result[t]result[j];j;}}else{if(getRank(rank_info,mod3_equal_zero_sort_result[i]1)getRank(rank_info,result[j]1)){merge_result[t]mod3_equal_zero_sort_result[i];i;}elseif(getRank(rank_info,mod3_equal_zero_sort_result[i]1)getRank(rank_info,result[j]1)){merge_result[t]result[j];j;}else{if(rank[mod3_equal_zero_sort_result[i]2]rank[result[j]2]){merge_result[t]mod3_equal_zero_sort_result[i];i;}else{merge_result[t]result[j];j;}}}}}for(;imod3_equal_zero_sort_result.size();i){merge_result[t]mod3_equal_zero_sort_result[i];}for(;jresult.size();j){merge_result[t]result[j];}for(size_t imerge_result.size()-original_tail,t0;imerge_result.size();i){SA[t]merge_result[i];}}voiddoDC3(stringstr){vectorstring::size_typerank_info(str.size());for(string::size_type i0;istr.size();i){rank_info[i]str[i]-96;}vectorstring::size_typeSA(str.size());DC3(rank_info,SA,27);cout后缀数组为endl;for(vectorstring::size_type::size_type i0;iSA.size();i){couti-SA[i] ;}coutendl;setstringtemp;for(inti0;istr.size();i){temp.insert(str.substr(i));}size_t j0;for(setstring::iterator ptemp.begin();p!temp.end();p){if(*p!str.substr(SA[j])){cout后缀数组计算结果错误endl;exit(-1);}j;}if(jSA.size()){cout后缀数组计算结果错误endl;exit(-1);}cout后缀数组计算结果正确endl;}intmain(){constintN20;string strba;/*string str; default_random_engine gen(time(nullptr)); for (size_t i 1; i N; i) { str.append(1, static_castchar(gen() % 26 97)); }*/cout求其后缀数组的字符串为strendl;doDC3(str);return0;}
