PAT 1005 后缀数组

#include <iostream>
#include <cstring>
using namespace std;

struct SuffixArray{//后缀数组
#ifndef _SA_
#define maxn 1200000
#define maxcnt 270
#endif
int n; //字符串长度
int sa[maxn]; //后缀数组, 排名为i的后缀的位置
int rk[maxn]; //名次数组,第i个位置开始的后缀排名
int ssa[maxn]; //保留后缀数组
int srk[maxn]; //保留名次数组
int cnt[maxn]; //计数数组
int height[maxn]; //排名相邻的两个后缀的最长公共前缀

void doubling(string s, int m)//倍增法计算后缀数组
{
//根据第一关键字进行基数排序
memset(cnt, 0, sizeof(cnt));
for(int i=0; i<s.length(); ++i) ++cnt[ rk[i] = s[i] ];
for(int i=1; i<m; ++i) cnt[i] += cnt[i-1];
for(int i=s.length()-1; i>=0; --i) sa[ --cnt[s[i]] ] = i;
for(int j=1, kk=1; kk < s.length(); j<<=1, m=kk)
{
//根据第二关键字进行基数排序,ssa为根据第二关键字排序后的后缀数组
int i;
for(i=s.length()-j, kk=0; i < s.length(); ++i) ssa[kk++] = i;
for(i=0; i < s.length(); ++i) if(sa[i] >= j) ssa[kk++] = sa[i] - j;
//根据第一关键字进行基数排序
for(i=0; i < s.length(); ++i) srk[i] = rk[ssa[i]];
memset(cnt, 0, sizeof(cnt));
for(i=0; i<s.length(); ++i) ++cnt[ srk[i] ];
for(i=1; i<m; ++i) cnt[i] += cnt[i-1];
for(i=s.length()-1; i>=0; --i) sa[ --cnt[srk[i]] ] = ssa[i];
memcpy(srk, rk, sizeof(rk));
for( rk[sa[0]] = 0, kk = 1, i = 1; i < s.length(); ++i )
{
rk[sa[i]] = (srk[sa[i-1]] == srk[sa[i]] && sa[i-1] + j < s.length() && sa[i] + j < s.length() && srk[sa[i-1] + j] == srk[sa[i] + j] )?kk-1:kk++;
}
}
}

void generateHeight(string s)//计算后缀最长公共前缀
{
int i, j, kk = 0;
// for(i=0; i<s.length(); ++i) rk[sa[i]] = i;
for(i=0; i<s.length(); height[rk[i++]] = kk)
{
if(rk[i]) for(kk?kk--:0, j = sa[rk[i]-1]; i+kk < s.length() && j+kk < s.length() && s[i+kk] == s[j+kk]; ++kk);
}

}
};
static SuffixArray sa;

int main()
{
ios::sync_with_stdio(false);
int N;
string s;
cin>>N;
getline(cin, s);
getline(cin, s);
sa.doubling(s, 130);
sa.generateHeight(s);
// for(int i=0; i<s.length(); ++i) cout<<sa.height[i]<<endl;//测试
int idx = sa.sa[0], ans = 0, maxL = 0;
for(int i=1; i<s.length(); ++i)
{
if(sa.height[i]>=N)
{
ans++;
}
else
{
ans = 0;
}
if(ans > maxL && s.length()-sa.sa[i] >= N)
{
maxL = ans;
idx = sa.sa[i];
}
}
cout<<s.substr(idx, N)<<" "<<maxL+1<<endl;
return 0;
}


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

PAT 1005 后缀数组

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » PAT 1005 后缀数组
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏