首页 > 代码库 > 字符串的最小表示法

字符串的最小表示法

2024-08-01 13:20:04   212人阅读

给定一个字符串，要求求出从某个下标开始，这个字符串的字典序最小，即字符串的最小表示法
比如字符串bbbaaa，从下标3开始表示为aaabbb，字典序最小

暴力算法的时间复杂度为O(n^3)
但是有线性的算法
初始时，让i=0，j=1，k=0；
分为三种情况，
①如果str[i+k] == str[j+k] k++;
②如果str[i+k] > str[j+k] i = i + k + 1, k = 0,  即最小表示不可能以str[i-->i+k]中的任一一个字符串开头
③如果str[i+k] < str[j+k] j = j + k + 1, k = 0, 同上

  str[i+k] > str[j+k]，不能以下标i开头是显然的，为什么,字符串的最小表示不可能以str[i-->i+k]中的任一一个字符串开头
  这个因为如果str[i+k]>str[j+k]，那么str[i+1->k] > str[j+1->k],str[i+2->k]>str[j+2->k]...str[i+k]>str[j+k]
  所以字符串的最小表示不可能以str[i-->i+k]中的任一一个字符串开头

 

zoj1729 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1729

 

 

 1 #include <stdio.h> 2 #include <string.h> 3 const int N = 100000+10; 4 char str[N]; 5 int minimalRepresentation() 6 { 7     int n = strlen(str); 8     int i = 0,j = 1, k = 0; 9     while(i<n && j<n && k<n)10     {11         int t = str[(i+k)%n] - str[(j+k)%n] ;12         if(t == 0)13             k++;14         else15         {16             if(t>0)17                 i+=k+1;18             else 19                 j+=k+1;20             if(i==j)21                 j++;22             k = 0;23         }24     }25     return i < j ? i : j;26 }27 int main()28 {29     int t;30     scanf("%d",&t);31     int n;32     while(t--)33     {34         scanf("%d",&n);35         scanf("%s",str);36         int index = minimalRepresentation();37         printf("%d\n",index);38     }39 }

 

字符串的最小表示法


联系
我们