delphij's Chaos

选择chaos这个词是因为~~实在很难找到一个更合适的词来形容这儿了……

02 Jul 2005

一个很有意思的问题(文本分类)

求一系列字符串的最长公共子串的问题大家都很了解,今天在琢磨垃圾信息的时候突然想到另一个问题。

好比说,5个字符串:

www.domain.com
domain.com
domain.net
www.domain.net
spammer.domain.net

希望将其排列成:

domain.com
domain.net
www.domain.com
www.domain.net
spammer.domain.net

或者说,希望domain.com和domain.net在包含它们的串之前,应该如何做?另外,如果给了一大堆*.domain.com,如何把domain.com挑出来?

一个很显然的方法是,将文本按照长度先排序一次,然后用某种方法在所有比它更长的串里面找其实例。但这种方法显然是有问题的,因为存在嵌套匹配的情况可以立即使这一算法弱化(自然,这并不是之前所提的问题的范畴);另外,其时间复杂性未免太高了一点。

看起来不那么简单。

欢迎探讨。


Archived: 1 Comment

atong | July 16, 2005 3:39 PM

是要找出 domain.com 么?
投机的方法,每行只有一个“.”的不就是了?嘿嘿~~