后缀数组的倍增算法的C++实现

倍增算法的详细解释见倍增算法讲解C代码实现为#includeiostream#includevector#includestring#includeset#includerandom#includectime#includealgorithmusingnamespacestd;voidradixSort(vectorintrank,vectorintresult,intradix_value,intoffset,vectorintsort_pos){vectorintbucket(radix_value,0);for(vectorint::size_type i0;isort_pos.size();i){bucket[rank[sort_pos[i]offset]];}for(vectorint::size_type i1;ibucket.size();i){bucket[i]bucket[i-1]bucket[i];}if(sort_pos.size()!0){for(vectorint::size_type isort_pos.size()-1;;--i){result[--bucket[rank[sort_pos[i]offset]]]sort_pos[i]offset;if(i0){break;}}}}boolcompareFisrTwo(vectorintrank,inti,intj,vectorintresult,intoffset){if(rank[result[i]]rank[result[j]]){if(result[i]offsetrank.size()result[j]offsetrank.size()){returntrue;}if(result[i]offsetrank.size()result[j]offsetrank.size()rank[result[i]offset]rank[result[j]offset]){returntrue;}}returnfalse;}voiddoMultiplication(conststringstr){vectorint*ranknewvectorint(str.size());vectorintsort_pos;for(inti0;istr.size();i){(*rank)[i]str[i]-97;sort_pos.push_back(i);}vectorintresult(str.size());radixSort(*rank,result,26,0,sort_pos);size_t k0;{vectorboolcheck_equal(26,false);for(;k(*rank).size();k){if(check_equal[(*rank)[k]]false){check_equal[(*rank)[k]]true;}else{break;}}}if(k(*rank).size()){intradix_value26;vectorint*_new_ranknewvectorint(str.size());for(intj1;;j1){for(inti0;ij;i){sort_pos[i]str.size()i;}inttj;for(inti0;iresult.size();i){if(result[i]j){sort_pos[t]result[i];}}radixSort(*rank,result,radix_value,-j,sort_pos);intcount0;boolhas_found_equalfalse;boolhas_pass_inequal_regionfalse;size_t rank_value0;for(inti1;iresult.size();i){(*_new_rank)[result[i-1]]rank_value;if(compareFisrTwo(*rank,i-1,i,result,j)){if(has_found_equalfalse){has_found_equaltrue;if(has_pass_inequal_region){has_pass_inequal_regionfalse;--count;}else{if(i!1)--count;}}}else{rank_value;if(has_found_equal){has_found_equalfalse;}else{has_pass_inequal_regiontrue;if(i1)count;}count;}}(*_new_rank)[result.back()]rank_value;swap(rank,_new_rank);if(countresult.size()){break;}radix_valuerank_value1;}}cout后缀数组为endl;for(inti0;iresult.size();i){couti-result[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(result[j])){cout后缀数组计算结果错误endl;exit(-1);}j;}if(jresult.size()){cout后缀数组计算结果错误endl;exit(-1);}cout后缀数组计算结果正确endl;vectorintheight(result.size());intpre_value_sub_one0;for(size_t i0;iheight.size();i){if((*rank)[i]0){height[(*rank)[i]]0;pre_value_sub_one0;}else{if(pre_value_sub_one!0)--pre_value_sub_one;size_t leftresult[(*rank)[i]-1];while(leftpre_value_sub_onestr.size()ipre_value_sub_onestr.size()str[leftpre_value_sub_one]str[ipre_value_sub_one]){pre_value_sub_one;}height[(*rank)[i]]pre_value_sub_one;}}coutheight数组为:;for(constautorun:height){coutrun ;}coutendl;}intmain(){constintN20;string strasddfas;/*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;doMultiplication(str);return0;}