信息学集训队作业0076-lsystem

题目0076–Lsystem（L系统）题目来源：Cerc96推荐者：高正宇英文原文L-systemAD0L(DeterministicLindenmayersystemwithoutinteraction)systemconsistsofafinitesetofsymbols(thealphabet),afinitesetPofproductionsandastartingstring.TheproductionsinPareoftheform,whereand(uiscalledtherightsideoftheproduction),isthesetofallstringsofsymbolsfromexcludingtheemptystring.Suchproductionsrepresentthetransformationofthesymbolxintothestringu.Foreachsymbol,Pcontainsexactlyoneproductionoftheform.Directderivationfromstringu1tou2consistsofreplacingeachoccurrenceofthesymbolinu1bythestringontherightsideoftheproductionforthatsymbol.ThelanguageoftheD0Lsystemconsistsofallstringswhichcanbederivedfromthestartingstringbyasequenceofthedirectderivations.Supposethatthealphabetconsistsoftwosymbolsaandb.Sothesetofproductionsincludestwoproductionsoftheforma,b,whereuandv,andthestartingstring.CanyouanswerwhetherthereexistsastringinthelanguageoftheD0Lsystemoftheformxzyforagivenstringz?(xandyaresomestringsfrom,isthesetofallstringsofsymbolsfrom,includingtheemptystring.).Certainlyyoucan.Writetheprogramwhichwillsolvethisproblem.InputTheinputfileoftheprogramconsistsofseveralblocksoflines.Eachblockincludesfourlines.Therearenoemptylinesbetweenanysuccessivetwoblocks.Thefirstlineofablockcontainstherightsideoftheproductionforthesymbola.Thesecondonecontainstherightsideoftheproductionforthesymbolbandthethirdonecontainsthestartingstringandthefourthlinethegivenstringz.Therightsidesoftheproductions,thegivenstringzandthestartingstringareatmost15characterslong.OutputForeachblockintheinputfilethereisonelineintheoutputfilecontainingYESorNOaccordingtothesolutionofthegivenproblem.SampleInputaabbabaaabbababbaSampleOutputYESNO二、中文翻译L系统给定只含有小写字母a,b的字符串w,s1,s2,z。其中s1,s2非空，并且所有字符串长度均不超过15。在w上施加若干次操作，每次操作把w中全部字符a替换为s1,同时把全部字符b替换为s2，得到新的w.问:最终能否得到一个字符串w含有给定子串z?如果可行，就输出‘YES’,否则输出‘NO’.输入 输入文件由多组测试数据组成。每组4排，各排依次是字符串w,s1,s2,z.组之间没有空排。输入文件由EOF符终止。输出 对每一组测试数据，相应的输出一排字符串，‘YES’或者‘NO’.样例输入aabbabaaabbababba样例输出YESNO三、初步讨论情况高正宇NP?方奇广度搜索侯启明想到算法了，但是没过，感觉数据有些问题……项荣璟应该是用类似动态规划的方法。但是如何优化到一个最低的复杂度呢？伍昱广搜可以么？只需要保存w中连续的15位，因为每次变化w的长度不会减少陆可昱初步的想法是从z串往前倒推。由于字符串长度不超过15，所以复杂度上应该没有问题的。许智磊有点像POI的Virus，也是处理无限长度01串的问题，应该是在字母树上考虑。邵煊程Bfs应该是能够解决的，但有没有不是搜索的方法呢？雷环中这道题可以从字符串Z出发逆向生成一系列不同的字符串（数量不多），然后看这些字符串中是否有W的子字符串即可。注意空串的处理。这道题可以从字符串Z出发按照s1->a,s2->b的法则逆向生成一系列不同的字符串（数量不多），注意首位的处理，然后看这些字符串中是否有W的子字符串即可。注意空串的处理。张宁这道题目可以倒过来做，从z串反过来缩小至w的子串，由于每次将s1，s2变为a，b，因此串长度只减不增，因此速度应该很快金恺极其简单的广搜，每次操作后只有连续的15位有用，所以状态总数为215（把每个串看成一个二进制数）。复杂度为O(215152)。王知昆可以用dp或记忆化搜索。因为起始串和目标串的长度不超过15，且每一位都是a或b，因此状态量不超过2^15,是可以接受的。张云亮与过去的一道天外来课一样，用宽搜，因为只有2^16的状态，对于每个字串，把他看成二进制，在把（‘1’+该串）换成十进制即表示他的状态值。刘一鸣常规的思路是从初始的w开始搜索，每次有两种可能的操作，一种是将所有的a换成s1，另一种则是将所有的b换成s2，这样下去，w会变得越来越大，空间上难以承受，时间上也会使判断s是不是w得字串变得很慢。所以，我们不妨反其道而行之：从s开始，将s1变为a，或将s2变为b。这样，s会越变越短，发现s是w的子串后即可退出。而s的长度显然不会超过15，我们将a看成1，b看成0，就可以将一个串转化成一个integer表示。因此就能用记忆化搜索来高效地解决此题了。常规的方法是顺着搜索，它的缺点是串的长度会不断变大。例如：S1=aabab,w=abababa(将所有的a变为S1)w=aababbaababbaababbaabab可以见到，w的长度是急剧变长的，这样一来，状态是极难表示、保存的。应对的方法是反其道而行之：将w中的S1换为a，或S2换为b，这样，w的长度只会变短而不会变长。而题目中说len(w)<=15，所以，我们可以用一个二进制数（0~32767）来表示w，非常易于判重，使搜索的速度得到了很大的提高。姜尚仆题目的意思是说：给定只含两种字母的源串w，和变换法则s1,s2，每次变换都把源串中两种字母换为s1,s2，问能否在若干次变换后生成z。这道题可以用搜索解决，从最后的字符串z出发，补齐它两头的字符，使它能用一个字符串经过一次变换得到。把它按变换法的逆过程生成它的源串，再一步一步倒着推，直到推出w的子串，就是找到了解。由于源串一定比目标串短。所以复杂度是很低的。另一种方法是顺着推，直到生成的串达到一定的长度，这个长度是多少，我还无法证明，或许它是错的。林希德因为“s1,s2非空”，所以无论怎样替换，串长都只增不减。又因为“字符串长度均不超过15”并且，所以搜索过程当中只有215种状态有意义，于是……动态规划吧。试题的中文翻译有问题：每次操作不应该是“把w中全部字符a替换为s1，同时把全部字符b替换为s2，得到新的w”，而应该是“某些a或者b被替换”吧？不然岂不成了模拟。何林这个题我用动态规划做的。Fa[i,j]表示字符’a’能不能匹配z中从第i位到第j位的子串。Fb[ij]表示字符’b’能不能匹配z中从第i位到第j位的子串。先把Fa,Fb都求出来，然后解决原问题就易如反掌了。另外高正宇的翻译是：“每次操作把w中全部字符a替换为s1”，我感觉“全部”二字甚为不妥。如果真是全部，那么连样例数据都出不来。饶向荣可以用广搜倒推来做，对于一个字串，看可由哪些字串获得