字符串斗转星移

字符串s="code", 循环左移可得到:"odec", "deco", "ecod"
对这s.size()个字符串排序可得"code"<"deco"<"ecod"<"odec". 那么, 最后的字符依次是e,o,d,c. 该尾字符序列是确定的
问题来了, 假如我们给定尾序列, 如何推演原字符串?

若字符没有重复, 还是很容易实现的

假设字符集是N, 那么O(N)的时间空间就可以搞定. 做法是通过为序列可以确定头序列, 那么就有很多的单向边 relationship[i] = tails[i]->heads[i], 最后得到一条直线

字符有重复

要区分codoocoodo. 这个姿态就有些像codility的题了. 依然使用无重复的方法, 考虑relationship[i]遇到的两类重复:

  1. heads[i]重复
    那么有
    X…S => SX… (k)

    S?..Y => YS?.. (i)
    假如?不是X, 而是某个i之后的j, 即:
    关系Z…S. 那么考虑YSX..和YSZ..显然前者会更早出现, 因为X<=Z. ?要出现只能是X
  2. tails[i]重复
    同样可证

依照对codility的评价规则, 这儿algorithm: 4.2, coding: 4.5, 之所以coding比algorithm还高, 因为coding我尝试了, 尚无满意的实现. 算法归纳为一句话: 若已出现了head/tail, 就用最早出现的, 实现时避免出现环

follow up

  • 1 能否给出一个非法的尾字符序列? 即不存在满足的原串
  • 2 如何测试程序?
    若采用正向的测试, 即如文章开头描述的方法, 给出s, 然后求出尾字符序列, 再根据尾字符序列求出s’, 那么你会怎么判断s’就是s的k(>=0)次循环左移得到的