hdu 4644 BWT (kmp)

看完题目你很容易想到，这个题目的关键点就是如何把给出的数组还原成原数组。

还原的原数组之后不管是AC自动机 还是 kmp都可以解决 - -虽然我觉得kmp会超时的感觉。

那么如何还原这个字符串就是在个题目的难点。。。

gc$aaac

1234567

排序之后变成了

$aaaccg

3456271

然后你按照排序后的下标依次走过去

会发现

$->a->c->a->a->c->g

3 5 2 4 6 7

也就恢复了原串。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define maxn 100186 using namespace std; struct node { char ch; int index; bool operator < (const node & cmp)const { return ch