一个判定性问题

gracias · 发表于 2009-12-23 17:48:06

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

刚才在一本书上看到这么一道题，不知怎么入手，特向大家请教，原文如下：二进制病毒审查委员会最近发现了如下规律：某些确定的二进制串是病毒的代码，如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找到了所有病毒代码段，试问：是否存在一个无限长的安全的二进制代码？例如：如果{011 ， 11 ，00000}为病毒代码段，那么一个可能的无限长的安全代码可以是010101.........。如果{01 ，11 ， 000000}为病毒代码段，那么就不存在一段无限长的安全代码。请写一个程序，读入病毒代码，判断是否存在一个无限长的安全代码。

mathe · 发表于 2009-12-23 17:58:48

这个应该可以通过有限自动机来解决

KeyTo9_Fans · 发表于 2009-12-23 20:04:57

给楼主看两张图。第一张图对应第一个例子：

第二张图对应第二个例子：

我先不做任何说明。有什么问题尽管问。

gracias · 发表于 2009-12-24 17:03:44

给楼主看两张图。第一张图对应第一个例子： 1511 第二张图对应第二个例子： 1512 我先不做任何说明。有什么问题尽管问。 KeyTo9_Fans 发表于 2009-12-23 20:04

太感谢兄弟这两张图了。构造一个这样的图，能找到一个不包含病毒串的环就存在一个无限长的安全串，否则就不存在。

litaoye · 发表于 2009-12-24 18:36:02

呵呵，这个帖子看的好眼熟呀！找环的方法要比我说的那种逐步缩短每个串的长度的方法看起来要好，至少程序写起来上比较直观，就是构造失配时回溯的节点还是比较复杂。

gracias · 发表于 2009-12-24 20:28:07

呵呵，这个帖子看的好眼熟呀！找环的方法要比我说的那种逐步缩短每个串的长度的方法看起来要好，至少程序写起来上比较直观，就是构造失配时回溯的节点还是比较复杂。 litaoye 发表于 2009-12-24 18:36

呵呵，csdn算法与数据结构->一道POI题

账号		自动登录	找回密码
密码			欢迎注册

[提问] 一个判定性问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分

评分

评分