打卡信奥刷题（3453）用C++实现信奥题 P10469 后缀数组

P10469 后缀数组题目描述后缀数组 (SA) 是一种重要的数据结构通常使用倍增或者 DC3 算法实现这超出了我们的讨论范围。在本题中我们希望使用快排、Hash 与二分实现一个简单的O(nlog⁡2n)O(n\log^2n)O(nlog2n)的后缀数组求法。详细地说给定一个长度为nnn的字符串SSS下标0∼n−10 \sim n-10∼n−1我们可以用整数k(0≤kn)k(0 \le k n)k(0≤kn)表示字符串SSS的后缀S(k∼n−1)S(k \sim n-1)S(k∼n−1)。把字符串SSS的所有后缀按照字典序排列排名为iii的后缀记为SAiSA_iSAi​。额外地我们考虑排名为iii的后缀与排名为i−1i-1i−1的后缀把二者的最长公共前缀的长度记为HeightiHeight_iHeighti​。特别地规定Height00Height_0 0Height0​0。我们的任务就是求出SASASA与HeightHeightHeight这两个数组。输入格式输入一个字符串其长度不超过3×1053 \times 10^53×105。字符串由小写字母构成。输出格式第一行为数组SASASA相邻两个整数用111个空格隔开。第二行为数组HeightHeightHeight相邻两个整数用111个空格隔开。输入输出样例 #1输入 #1ponoiiipoi输出 #19 4 5 6 2 8 3 1 7 0 0 1 2 1 0 0 2 1 0 2C实现#includebits/stdc.husingnamespacestd;#defineullunsignedlonglongconstintN3e510;constintBASE131;chars[N];intn;ull hash1[N],pw[N],sa[N];ullgethash(intl,intr){returnhash1[r]-hash1[l-1]*pw[r-l1];}intgetlen(inta,intb){// a,b 最长公共前缀长度intl0,rmin(n-a,n-b)1;while(lr){intmid(lr1)/2;if(gethash(a,amid-1)gethash(b,bmid-1))lmid;elsermid-1;}returnl;}boolcmp(inta,intb){intlengetlen(a,b);returns[alen]s[blen];// 比较最长公共前缀的后一个字母的大小}signedmain(){cin(s1);nstrlen(s1);pw[0]1;for(inti1;in;i){hash1[i]hash1[i-1]*BASEs[i];}for(inti1;in;i){pw[i]pw[i-1]*BASE;sa[i]i;}sort(sa1,sa1n,cmp);for(inti1;in;i){coutsa[i]-1 ;}cout\n;for(inti0;in;i){coutgetlen(sa[i],sa[i1]) ;}cout\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容