【tyvj1860】后缀数组

2014年9月4日2,4506
描述 Description
我们定义一个字符串的后缀suffix(i)表示从s[i]到s[length(s)]这段子串。
后缀数组(Suffix array)SA[i]中存放着一个排列,满足suffix(sa[i])<suffix(sa[i+1]) 按照字典序方式比较
定义height[i]表示suffix(sa[i])与suffix(sa[i-1])之间的最长公共前缀长度,其中height[1]=0
你的任务就是求出SA和height这两个数组。字符串长度<=200000
输入格式 InputFormat
一行,为描述中的字符串(仅会出现小写字母)
输出格式 OutputFormat
共两行,每行n个数,第一行为sa[i],第二行为height[i],其中每行的数均用空格隔开

样例输入 SampleInput

aabaaaab

样例输出 SampleOutput 

4 5 6 1 7 2 8 3
0 3 2 3 1 2 0 1

题解

 

  • conic2015年3月17日 上午11:26 回复

    你的代码TLE了..你当年做了什么让它A掉的..

    #1  
    • >_2015年3月17日 下午4:19 回复

      数据加强过了O.O……

      #11
      • conic2015年3月17日 下午5:10 回复

        我已换fgets读入和putchar输出 效率提高了20多倍

        #12
        • 翁家翌2015年3月18日 下午5:55 回复

          应该用fread和fwrite才是正确姿势= =

          #13
  • heoi20152015年5月19日 下午3:54 回复

    大神从哪里学的后缀数组,能不能给个地址或者资料

    #2  
    • hzwer2015年5月19日 下午4:13 回复
      admin

      后缀数组处理字符串的有力工具

      #21