网站做什么推广好,网站域名注册步骤,做公司网站需要学哪些,网站背景音乐循环字符串的最小表示法的问题可以这样描述#xff1a; 对于一个字符串S#xff0c;求S的循环的同构字符串S’中字典序最小的一个。 由于语言能力有限#xff0c;还是用实际例子来解释比较容易#xff1a;设Sbcad#xff0c;且S’是S的循环同构的串。S’可以是bcad或者cad…循环字符串的最小表示法的问题可以这样描述 对于一个字符串S求S的循环的同构字符串S’中字典序最小的一个。 由于语言能力有限还是用实际例子来解释比较容易设Sbcad且S’是S的循环同构的串。S’可以是bcad或者cadb,adbc,dbca。而且最小表示的S’是adbc。对于字符串循环同构的最小表示法其问题实质是求S串的一个位置从这个位置开始循环输出S得到的S’字典序最小。一种朴素的方法是设计i,j两个指针。其中i指向最小表示的位置j作为比较指针。 令i0,j1如果S[i] S[j] ij, ji1如果S[i] S[j] j如果S[i]S[j] 设指针k分别从i和j位置向下比较直到S[i] ! S[j] 如果S[ik] S[jk] ij,ji1 否则j返回i 起初我想在j指针后移的过程中加入一个优化。就是j每次不是加1而是移动到l位置。其中lj且S[l]S[j]。但是即使加入这一优化在遇到bbb…bbbbbba这样的字符串时复杂度将退化到O(n^2)。 注意到朴素算法的缺陷在于斜体的情况下i指针的移动太少了。针对这一问题改进就得到了最小表示法的算法。最小表示法的算法思路是维护两个指针i,j。 令i0,j1如果S[i] S[j] ij, ji1如果S[i] S[j] j如果S[i]S[j] 设指针k分别从i和j位置向下比较直到S[i] ! S[j] 如果S[ik] S[jk] iik 否则j返回i和j的小者 注意到上面两个算法唯一的区别是粗体的一行。这一行就把复杂度降到O(n)了。值得一提的是与KMP类似最小表示法处理的是一个字符串S的性质而不是看论文时给人感觉的处理两个字符串。应用最小表示法判断两个字符串同构只要将两个串的最小表示求出来然后从最小表示开始比较。剩下的工作就不用多说了。 [cpp] view plaincopy int MinimumRepresentation(char *s, int l) { int i 0, j 1, k 0, t; while(i l j l k l) { t s[(i k) l ? i k - l : i k] - s[(j k) l ? j k - l : j k]; if(!t) k; else{ if(t 0) i i k 1; else j j k 1; if(i j) j; k 0; } } return (i j ? i : j); } http://acm.timus.ru/problem.aspx?space1num1423 这个题目可以练练手也可用KMP 转载于:https://www.cnblogs.com/PegasusWang/archive/2013/05/28/3104851.html
