模板

int getMin(char *s)  {      int i = 0, j = 1, l;      int len = strlen(s);      while(i < len && j < len)      {          for(l = 0; l < len; l++)              if(s[(i + l) % len] != s[(j + l) % len]) break;          if(l >= len) break;          if(s[(i + l) % len] > s[(j + l) % len])          {              if(i + l + 1 > j) i = i + l + 1;              else i = j + 1;          }          else if(j + l + 1 > i) j = j + l + 1;          else j = i + 1;      }      return i < j ? i : j;  }    int getMax(char *s)  {      int len = strlen(s);      int i = 0, j = 1, k = 0;      while(i < len && j < len && k < len)      {          int t = s[(i+k)%len]-s[(j+k)%len];          if(!t) k++;          else          {              if(t > 0)              {                  if(j+k+1 > i) j = j+k+1;                  else j = i+1;              }              else if(i+k+1 > j) i = i+k+1;              else i = j+1;              k = 0;          }      }      return i < j ? i : j;  }

 

问题提出 : 给出一个字符串求出字符串的最大or最小表示法

 

分析 : 参考==>

一般来说就是能够解决字面意思的题意以及一些字符串同构问题

 

相关题目 :

①

题意 : 给出 n 个字符串，问你有多少不同的字符串，其中同构的字符串算作一种

分析 : 用最大or最小表示法将所有字符串“同化”然后装到set容器判重

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;int len;int getMin(string & s){ int i = 0, j = 1, l; while(i < len && j < len) { for(l = 0; l < len; l++) if(s[(i + l) % len] != s[(j + l) % len]) break; if(l >= len) break; if(s[(i + l) % len] > s[(j + l) % len]){ if(i + l + 1 > j) i = i + l + 1; else i = j + 1; } else if(j + l + 1 > i) j = j + l + 1; else j = i + 1; } return i < j ? i : j;}int main(void){ int n; string s, into; while(~scanf("%d", &n)){ set
            
              cnt; for(int i=0; i
             
              >s; len = s.length(); int idx = getMin(s); into.clear(); for(int j=0; j
             
            
           
          
         
        
       
      

 

②

题意 : 给出一个字符串，叫你给出要构成最大or最小表示法字符串开头应该在的位置，然后就是计算一下这个表示法下字符串循环节出现次数

分析 : KMP + 最大最小模板即可解决

#include
      
       #include
       
        using namespace std;const int maxn = 1e6 + 10;char mo[maxn], s[maxn];int Next[maxn], moL, len;int getMax(){    int i = 0, j = 1, k = 0;    while(i < len && j < len && k < len)    {        int t = s[(i+k)%len]-s[(j+k)%len];        if(!t) k++;        else        {            if(t > 0)            {                if(j+k+1 > i) j = j+k+1;                else j = i+1;            }            else if(i+k+1 > j) i = i+k+1;            else i = j+1;            k = 0;        }    }    return i < j ? i : j;}int getMin(){    int i = 0, j = 1, l;    while(i < len && j < len)    {        for(l = 0; l < len; l++)            if(s[(i + l) % len] != s[(j + l) % len]) break;        if(l >= len) break;        if(s[(i + l) % len] > s[(j + l) % len]){            if(i + l + 1 > j) i = i + l + 1;            else i = j + 1;        }        else if(j + l + 1 > i) j = j + l + 1;        else j = i + 1;    }    return i < j ? i : j;}inline void GetNext(){    int i = 0, j = -1;    Next[i] = j;    while(i < moL){        while(j!=-1 && mo[i]!=mo[j]) j = Next[j];        Next[++i] = ++j;    }}inline void PrintAns(){    int idx = getMin();    for(int i=0; i