{algorithm}{discussion}string matching

[fihopzz]

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.

[Wu Yin]

try to construct a suffix tree or suffix array in O(n) time

--
滚滚长江东逝水，浪花淘尽英雄。
是非成败转头空。
青山依旧在，几度夕阳红。
白发渔樵江渚上，惯看秋月春风。
一壶浊酒喜相逢。
古今多少事，都付笑谈中。

[飞天鱼]

KMP匹配。

把AA串写两份，a1a2a3...ana1a2a3...an

拿B串去匹配。

 

2009/12/3 fihopzz <xia...@gmail.com>

[chen_xu]

先将A自己接上自己，即AA = a1a2...an a1a2...an，这一步是O(1).
然后判断AA中是否包含B，这一步可以用KMP算法，是O(n)的
所以总时间是O(n).

[raymond]

repleat B and search A in B
BM string searching algorithm is fast than BMP, i have written an
introduction.
http://ysqraymond.spaces.live.com/?_c11_BlogPart_BlogPart=blogview&_c=BlogPart&partqs=cat%3Dimage%2520process

On 12月3日, 上午12时30分, fihopzz <xiao...@gmail.com> wrote:

[fihopzz]

Thanks. I think this is the simple way.

On Dec 2, 8:03 pm, 飞天鱼 <feitia...@gmail.com> wrote:
> KMP匹配。
> 把AA串写两份，a1a2a3...ana1a2a3...an
> 拿B串去匹配。
>

> 2009/12/3 fihopzz <xiao...@gmail.com>

[fihopzz]

Yes, Thanks.

[fihopzz]

OK, thanks.

On Dec 3, 5:26 am, raymond <shiqu...@gmail.com> wrote:
> repleat B and search A in B
> BM string searching algorithm is fast than BMP, i have written an

> introduction.http://ysqraymond.spaces.live.com/?_c11_BlogPart_BlogPart=blogview&_c...