最小表示法
whitedeath
posted @ 2010年5月26日 04:12
in Life
, 5117 阅读
最小表示法是由IOI2003年冬令营的周源提出来的，今天学习了这后，写下自己的理解和感想~
什么叫最小表示呢，就是把这个字符串看作一个环，在转动的过程中，那个字典序最小的字符串即为字符串的最小表示，具体定义可以参照ZOJ 1729：acm.zju.edu.cn/onlinejudge/showProblem.do
周源同学介绍的时候是以求两个字符串是否是同构的为中心介绍的，而在求单个字符串的最小表示法上没有细说，个人感觉这个更难以理解一点，因为它相当于自己和自己的下一个表示求是否同构，这个过程中，求出最小表达式，就像kmp算法的next数组，是自己匹配自己的结果~
这个是网上最一般的最小表示法代码：
int MinimumRepresentation(char *s, int len)
{
int i = 0, j = 1, count = 0, t;
while (i < len && j < len && count < len)
{
if(s[(i + count) % len] == s[(j + count) % len])
count++;
else
{
if (s[(i + count) % len] > s[(j + count) % len])
i = i + count + 1;
else
j = j + count + 1;
if (i == j) ++j;
count = 0;
}
}
return min(i,j);
}
然而，我在理解这个算法的过程中、和同学讨论的过程中，逐渐发现一些可以改进的地方：
首先，求余过程很费时间，尤其是字符串比较长的时候。而且本题中最多是len的2倍，所有变求余为作差；
其次，最后的return min(i,j)可以改成直接return i，因为i <= j是肯定的....因为用通俗的说法，每次i都会把j拉到i+1的位置，所以最后，可以在改变i的时候，将j也拖过去....
最终代码：
int MinimumRepresentation(char *s, int len)
{
int i = 0, j = 1, count = 0, t;
while (i < len && j < len && count < len)
{
x = i + count;
y = j + count;
if (x >= len) x -= len; //用减法代替求余
if (y >= len) y -= len; //用减法代替求余
if (s[x] == s[y])
count++;
else
{
if (s[x] > s[y])
{
i = i + count + 1;
j = i + 1; /*将 j 拖至 i + 1 的地方*/
}
else
j = j + count + 1;
if (i == j) j++;
count = 0;
}
}
return i; //直接return i即可
}
思路：这个算法其实就是这样子的，就像刚才说的，是自己跟自己的下一个表示比较，其中i代表本身，j代表这个环的下一个表示方法，然后比较，如果j的表示方法比i小，i就更新了，同时j也更新至i的下一个表示方法，然后继续匹配，直到字符串尾。
- 无匹配
2011年7月19日 22:01
你这样把j强行拉到i+1是不对的，会造成复杂度达到N^2比如一个递增序列然后最后是个最小的如bcdefa，这样就会达到N^2
2012年8月23日 22:44
@isnowfy:
确实是这样，复杂度变为 N^2 了 减法代替取余应该没错吧
2021年2月27日 17:12
I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks... putlocker
2021年9月01日 16:53
The career of child-rearing involves addressing lots with mess. Moms (primarily housewives) will be mostly involved with messy job opportunities. Sometimes they can be found wiping its sticky fingers and various times they can be sorting by mental discord. For these folks, the basis of calmness for a little bit tends that they are painfully incredibly elusive. For these folks, standard home cleaning services will be nothing not as much as a bonus. The moods with moms were observed to swap for more suitable, once its household cleaning up work accomplishes.
2022年8月25日 13:03
Aspirants can Download the Subject Wise JKBOSE 11th Class Important Model Question Paper 2023 Which are Available in This Article. Those Candidates who Started Their Preparation for the JKBOSE 11th Class Examinations Must Include These JKBOSE 11th Important Model Question Paper 2023 in the Preparation. JKBOSE +1 Model Paper 2023 And, Gain Complete Knowledge on all Subjects and Give Your Best in the Examination. All Subject wise JKBOSE Class 11th Previous Important Model Question Paper 2023 PDF’s are Provided at the End of the Page. Scroll Down to the Page to get all Details About the J&K 11th Class Important Model Question Paper 2023.
2022年9月22日 01:01
NCERT Sample Paper 2023 Pdf Download for 1st, 2nd, 3rd, 4th, 5th, 7th, 8th, 9th, 10th, 11th & 12th Standard Sample Pape Suggestions for Hindi Medium, English Medium & Urdu Medium students studying at CBSE, KVS, NCERT Sample Paper Pdf Download JNV and other Central & State Education Boards of the Countr.NCERT Sample Paper 2023 Pdf Download for 1st, 2nd, 3rd, 4th, 5th, 7th, 8th, 9th, 10th, 11th & 12th Standard Sample Pape Suggestions for Hindi Medium, English Medium & Urdu Medium students studying at CBSE, KVS, JNV and other Central & State Education Boards of the Country…
2024年1月30日 21:59
One good thing about a wholesale paintings that are being sold from virtual stores is this distinguishing these folks from primary oil paintings is next to impossible. Right with the same bumpy brush strokes to your vibrant colorations, not many will make outside the difference together with the reproduction paintings that are being sold from general suppliers internet. It runs without saying that you first however decide your capacity to pay.