如何快速检验两个字符串是否循环相等？

http://groups.google.com/group/pongba/browse_thread/thread/ef768fca7ff84cad?hl=zh-CN
The input is two strings of characters A = a1a2...an and B =
b1b2...bn.Design an O(n) algorithm to determine whether B is a cyclic
shift of A. In other words, the algorithm should determine whether
there exists an index k, 1<=k<=n such that ai = b(k+i)modn, for all i,
1<=i<=n.

很郁闷，groups好像都被墙了，反正我在任何地方都上不去。

答案如此简单：

KMP匹配。
把AA串写两份，a1a2a3...ana1a2a3...an
拿B串去匹配。

matrix67写了一篇很详细的KMP算法介绍
http://www.matrix67.com/blog/archives/115

提到了字符串匹配的其他方法：suffix tree (很多地方用到了的，差分算法里) 和 自动机(好像est大神在blog讲过)
唉，不懂的东西太多了