资源描述：
《浅析“最小表示法”思想在字符串循环同构问题中的应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用安徽省芜湖市第一中学周源【目录】5.1-9,,services,andmakethecitymoreattractive,strengtheningpublictransportinvestment,establishedasthebackboneoftheurbanrailtransitmulti-level,multi-functionalpublictransportsystem,thusprote
2、ctingtheregionalpositionandachieve浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源浅析“最小表示法”思想在字符串循环同构问题中的应用1【目录】1【摘要】2【关键字】2【正文】31、问题引入31.明确几个记号和概念32.问题32、枚举算法和匹配算法31.枚举算法32.匹配算法33.小结43、最小表示法思想41.“最小表示法”思想的提出42.“最小表示法”思想的定义43.“最小表示法”在本题的应用54.模拟算法执行75.小结84、总结85.1-9,,services,an
3、dmakethecitymoreattractive,strengtheningpublictransportinvestment,establishedasthebackboneoftheurbanrailtransitmulti-level,multi-functionalpublictransportsystem,thusprotectingtheregionalpositionandachieve浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源5.1-9,,services,andmaketh
4、ecitymoreattractive,strengtheningpublictransportinvestment,establishedasthebackboneoftheurbanrailtransitmulti-level,multi-functionalpublictransportsystem,thusprotectingtheregionalpositionandachieve浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源【摘要】最小表示法在搜索判重、判断图的同构等很多问题中有着重要的
5、应用。本文就围绕字符串循环同构的判断这个问题，在很容易找到O(N)的匹配后，本文引进的“最小表示法”思想，并系统的对其下了定义，最后利用“最小表示法”思想构造出了更优秀，更自然的算法。无论是增加“最小表示法”思想这方面的知识，提高增加竞赛中的综合素质，相信本文对同学们还是有所裨益的。【关键字】字符串循环同构匹配最小表示法浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源【正文】1、问题引入1.明确几个记号和概念由于本篇论文主要讨论与字符串有关的算法，所以在本文中，一切未经说明的以开头的变量均表示字符串。
6、⑴．，即的长度。⑵．为的第个字符。这里。⑶．，即截取出的第个字符到第个字符的子串。这里。特别的，。⑷．定义的一次循环；而的次循环，的零次循环。⑸．如果字符串可以经过有限次循环得到，即有，则称和是循环同构的。⑹．设有两个映射，定义和的连接，这里。——这个定义用于后文算法描述中。2.问题给定两个字符串和，，判断他们是否循环同构。2、枚举算法和匹配算法1.枚举算法很容易知道，的不同的循环串最多只有个，即，所以只需要把他们一一枚举，然后分别与比较即可。枚举算法思维简单，易于实现，而它的时间复杂度是级这里N=
7、s1
8、=
9、
10、s2
11、。，已经可以胜任大多数问题的要求了。然而如果大至几十万，几百万，枚举算法就无能为力了，有没有更优秀的算法呢？2.匹配算法从枚举算法执行过程中很容易发现，枚举算法的本质就是在一个可以循环的字符串浅析“最小表示法”思想在字符串循环同构问题中的应用安徽周源中寻找的匹配，于是联想到模式匹配的改进算法是级的，那么在循环串中寻找匹配是不是也有线性的算法呢？回答是肯定的：由于循环串与一般的字符串本质的区别就是前者是“循环”的，如果能去掉“循环”这个限制，那么就可以直接套用一般字符串的模式匹配算法了！显然，将复制两次：做
12、为主串，则任何与循环同构的字符串至少都可以在中出现一次，于是可以说就是循环串的一般字符串形式！问题成功转化为求在中的模式匹配。——这完全可以在级时间内解决。1.小结很容易得到的枚举算法显然不能满足大数据的要求，于是我们从算法的执行过程入手，探查到了枚举算法的实质：模式匹配。最后，通过巧妙的构造、转换模型，直接套用模式匹配算法，得到了级别的算法。但是问题是否已经完美解决了呢？也许你会说：
