最小表示法

1、HDU 3374 String Problem(见《KMP专题》15)

2、hdu 2609 How many（见《KMP专题》16）

3、uva 1314 Hidden Password

　　题意：给出一个字符串，求其最小表示法。

　　思路：最小表示法模板

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4 int len;
 5 const int maxn = 100010;
 6 char Str[maxn];
 7 //求最小表示的起始坐标
 8 int getMin()
 9 {
10     int i = 0, j = 1, k = 0;//i和j是两个进行比较的起始匹配位点，k是匹配长度
11     while (i< len && j< len&&k<len)
12     {
13         if (Str[(i + k) % len] == Str[(j + k) % len])
14             k++;//如果相同，匹配长度增大，比较位置向移
15         else//如果不同，则字典序大的位置肯定不会是答案，改变那个匹配位点
16         {
17             if (Str[(i + k) % len] > Str[(j + k) % len])//已经有{ Str[i]~Str[i + k - 1] == Str[j]~Str[j + k - 1]了，且有Str[i + k]>Str[j + k]，自然我们选i~i + k中的任意一点都是比j~j + k的相应位置要差的，所以自然可以都略过
18                 i += k + 1;
19             else
20                 j += k + 1;
21             k = 0;
22             if (i == j)//若滑动后i == j那么j++,保证错开
23                 j++;
24         }
25     }
26     return min(i, j);//因为字典序大的位置被后移了，所以较小的位置就是答案
27 }
28 int main()
29 {
30     int t;
31     scanf("%d", &t);
32     while (t--)
33     {
34         scanf("%d%s", &len, Str);
35         printf("%d
", getMin());
36     }
37     return 0;
38 }

View Code