Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1072469
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类: Python/Ruby

2012-02-01 18:48:50

在scheme/planet上又看到了这道经典的面试题:写一个函数,判断字符串s1是否是s2循环移位得到的。
例如"WriteCode"就可以由"CodeWrite"循环移位得到。

一个trivial的实现如下。
有两个问题还没有想清楚:
1. 是否有更高效的算法?(可以用KMP找子串)
2. substring-at?和compare是尾递归吗?

  1. #lang racket/base

  2. ; findout if pat is substring of str
  3. (define (substring? pat str)
  4.   (define pat-len (string-length pat))
  5.   (define str-len (string-length str))
  6.   (let substring-at? ((from 0))
  7.     (if (> (+ pat-len from) str-len)
  8.       #f
  9.       (let compare ((index 0))
  10.         (cond
  11.           ((>= index pat-len) #t)
  12.           ((char=? (string-ref pat index)
  13.                    (string-ref str (+ from index)))
  14.            (compare (+ index 1)))
  15.           (else (substring-at? (+ from 1))))))))

  16. ; if s1 is a rotation of s2
  17. ; eg: ProgramRacket is a rotation of RacketProgram
  18. (define (rotate-str? s1 s2)
  19.   (and (= (string-length s1)
  20.           (string-length s2))
  21.        (substring? s1 (string-append s2 s2))))

  22. ; main starts here
  23. (if (rotate-str?
  24.       (vector-ref (current-command-line-arguments) 0)
  25.       (vector-ref (current-command-line-arguments) 1))
  26.   (printf "Yes\n")
  27.   (printf "No\n"))
阅读(3989) | 评论(0) | 转发(0) |
0

上一篇:2012年度努力方向

下一篇:httpclient

给主人留下些什么吧!~~