hdu5558 Alice's Classified Message
地址:http://acm.split.hdu.edu.cn/showproblem.php?pid=5558
题目:
Alice's Classified Message
Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 789 Accepted Submission(s): 311
S[a…b] means a substring of S ranging from S[a] to S[b] (0≤a≤b<N). If the first i letters have been encrypted, Alice will try to find a magic string P. Assuming P has K letters, P is the longest string which satisfies P=S[T...T+K−1] (0≤T<i,T+K≤N) and P=S[i…i+K−1](i+K≤N). In other words, P is a substring of S, of which starting address is within [0...i−1], and P is also a prefix of S[i...N−1]. If P exists, Alice will append integer K and T to ciphertext. If T is not unique, Alice would select the minimal one. And then i is incremented by K. If P does not exist, Alice will append -1 and the ASCII code of letter S[i] to ciphertext, and then increment i by 1.
Obviously the first letter cannot be encrypted. That is to say, P does not exist when i=0. So the first integer of ciphertext must be -1, and the second integer is the ASCII code of S[0].
When i=N, all letters are encrypted, and Alice gets the final ciphertext, which consists of many pairs of integers. Please help Alice to implement this method.
aaaaaa
aaaaabbbbbaaabbc
-1 97
5 0
Case #2:
-1 97
4 0
-1 98
4 5
5 2
-1 99
#include <bits/stdc++.h>
using namespace std;
struct SAM
{
static const int MAXN = <<;//大小为字符串长度两倍
static const int LetterSize = ; int tot, last, ch[MAXN][LetterSize], fa[MAXN], len[MAXN];
int sum[MAXN], tp[MAXN], cnt[MAXN]; //sum,tp用于拓扑排序,tp为排序后的数组
int ft[MAXN];
void init( void)
{
last = tot = ;
len[] = ;
memset( ch[], , sizeof ch[]);
} void add( int x, int pos)
{
int p = last, np = last = ++tot;
len[np] = len[p] + , cnt[np] = , ft[np] = pos;
memset( ch[np], , sizeof ch[np]);
while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];
if( p == )
fa[np] = ;
else
{
int q = ch[p][x];
if( len[q] == len[p] + )
fa[np] = q;
else
{
int nq = ++tot;
memcpy( ch[nq], ch[q], sizeof ch[q]);
len[nq] = len[p] + , fa[nq] = fa[q], fa[q] = fa[np] = nq, ft[nq] = ft[q];
while( p && ch[p][x] == q) ch[p][x] = nq, p = fa[p];
}
}
} void toposort( void)
{
for(int i = ; i <= len[last]; i++) sum[i] = ;
for(int i = ; i <= tot; i++) sum[len[i]]++;
for(int i = ; i <= len[last]; i++) sum[i] += sum[i-];
for(int i = ; i <= tot; i++) tp[sum[len[i]]--] = i;
for(int i = tot; i; i--) ft[fa[i]] = min(ft[fa[i]],ft[i]);
} void go(char *ss)
{
toposort();
for(int i=,n=len[last],p,j;i<n;i++)
{
for(p=,j=;;j++)
{
int c=ss[i+j]-'a';
if(!(i+j<n&&ch[p][c]&&ft[ch[p][c]]-j<i))
break;
p=ch[p][c];
}
j--;
if(p==)
printf("-1 %d\n",(int)ss[i]);
else
printf("%d %d\n",j+,ft[p]-j),i+=j;
}
}
} sam; char ss[]; int main(void)
{
//freopen("in.acm","r",stdin);
int t,cs=;cin>>t;
while(t--)
{
sam.init();
scanf("%s",ss);
for(int i=,len=strlen(ss);i<len;i++) sam.add(ss[i]-'a',i);
printf("Case #%d:\n",cs++);
sam.go(ss);
}
return ;
}
最新文章
- Spark中决策树源码分析
- JS调用OC方法并传值,OC调用JS方法并传值////////////////////////zz
- javascript高级程序设计---Event对象三
- 捕获Insert触发器失败记录
- paip.java c++得到当前类,方法名称以及行号
- Queue及Stack
- IOS 四种保存数据的方式
- Oracle SQL的硬解析、软解析、软软解析
- Ext.Net学习笔记16:Ext.Net GridPanel 折叠/展开行
- selenium IDE处理各种窗口问题解决方法
- iOS推送 再备
- CentOS 5 安装Oracle10g
- 用bat 删除当前文件夹下的某类文件
- [leetcode-516-Longest Palindromic Subsequence]
- Ambari安装之部署单节点集群
- java里程碑之泛型--泛型方法
- mfc基于对话框的简单四则运算计算器
- MySQL zip版本安装
- java之Spring集成CXF简单调用
- redis安装--集群