注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

1031: [JSOI2007]字符加密Cipher  

2014-11-21 19:26:13|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1031: [JSOI2007]字符加密Cipher

研究了快一天……应用的部分还没开始看Q.Q
虽然一开始代码不是很好理解,但是理解了之后就觉得很好写了
不过还是有不少细节需要注意
应该算是经典测模板题了
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int LEN = 2E5+10;
int n,m,Sa[LEN];
char str[LEN];
namespace Suf{
int tmp[2][LEN],cot[LEN],lt[LEN];
//const char MINC = min(min('a','A'),'0');
void sort(char s[],int n,int sa[]){
int i,j,p,*x=tmp[0],*y=tmp[1];
int m = 'z'+1;
//first sort
for(i=0;i<m;i++)cot[i]=0;
for(i=0;i<n;i++)cot[x[i]=s[i]]++;
for(i=1;i<m;i++)cot[i]+=cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[x[i]]]=i;

for(j=1;j<=n;j*=2,m=p){
//sort 2
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<n;i++)lt[i] = x[y[i]];
//sort 1
for(i=0;i<m;i++)cot[i]=0;
for(i=0;i<n;i++)cot[lt[i]]++;
for(i=1;i<m;i++)cot[i]+=cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[lt[i]]]=y[i];
//calc x[]
swap(x,y);p=1;x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]] = y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j] ? p-1:p++;
}
}
}
int scan(){int i=0;scanf("%d",&i);return i;}
int main(){
//freopen("in.txt","r",stdin);
int i,j,len;
scanf("%s",str);
len = strlen(str);

for(i=0;i<len;i++)str[i+len]=str[i];
str[len*2]=0;
Suf::sort(str,len*2,Sa);

//for(i=0;i<len;i++)printf("%d ",Sa[i]);

for(i=0;i<len*2;i++)
if(Sa[i]<len){
printf("%c",str[Sa[i]+len-1]);
}
return 0;
}

题解:
后缀数组
首先把字符串复制一遍,处理好之后扫一遍sa[]如果sa[i]<原长就输出
  评论这张
 
阅读(16)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017