hdu 3374 String Problem

点击打开链接hdu 3374

思路：求最小/最大表示+kmp匹配

分析：
1 题目要求给定一个字符串求出最小和最大表示的rank和出现的times。
2 如果直接暴力枚举n 最大10^6肯定TLE，所以这了应该要用到的是求解一个字符串的最小和最大表示，然后利用kmp去匹配查找出现的次数
3 在利用kmp匹配的时候应该要注意不能多算，比如有abcder,那么用abcder去匹配abcderabcder的时候就有两次的匹配结果，但实际上这里只有一个，所以这个地方要注意。

代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define MAXN 2000010

int len;
int next[MAXN/2];
char String[MAXN];
char minString[MAXN/2] , maxString[MAXN/2];
int minTimes , maxTimes;
int minRank , maxRank;

/*求最小表示的起始坐标*/
int getMin(){
   int i = 0 , j = 1 , k = 0;
   while(i+k < len && j+k < len){
      if(String[i+k] == String[j+k])
        k++;
      else{
        if(String[i+k] > String[j+k])
           i = i+k+1;
        else
           j = j+k+1;
        k = 0;
        if(i == j)/*若滑动后i == j那么j++*/
           j++;
      }
   }
   return min(i , j);
}

/*求最大表示的起始坐标*/
int getMax(){
   int i = 0 , j = 1 , k = 0;
   while(i+k < len && j+k < len){
      if(String[i+k] == String[j+k])
        k++;
      else{
        if(String[i+k] < String[j+k])
           i = i+k+1;
        else
           j = j+k+1;
        k = 0;
        if(i == j)/*若滑动后i == j那么j++*/
           j++;
      }
   }
   return min(i , j);
}

/*求出最小表示*/
void getMinString(){
   int pos = 0;
   for(int i = minRank ; i < minRank+len/2 ; i++)
      minString[pos++] = String[i];
   minString[pos] = '\0';
}

/*求出最大表示*/
void getMaxString(){
   int pos = 0;
   for(int i = maxRank ; i < maxRank+len/2 ; i++)
      maxString[pos++] = String[i];
   maxString[pos] = '\0';
}

/*求next数组*/
void getNext(char *pattern){
    int m = strlen(pattern);
    next[0] = next[1] = 0;

    for(int i = 1 ; i < m ; i++){
       int j = next[i];
       while(j && pattern[i] != pattern[j])
          j = next[j];
       next[i+1] = pattern[i] == pattern[j] ? j+1 : 0;
    }
}

/*kmp匹配找到有几个*/
int find(char *pattern){

   int count = 0;
   int m = strlen(pattern);
   int j = 0;

   for(int i = 0 ; i < len-1 ; i++){/*这里只要判断到len-1即可，这样就可以避免多算了一次*/
      while(j && pattern[j] != String[i])
          j = next[j];
      if(pattern[j] == String[i])
          j++;
      if(j == m)
          count++;
   }
   return count;
}

int main(){
   while(scanf("%s" , String) != EOF){

      int flag;
      char tmp[MAXN];
      memcpy(tmp , String , sizeof(String));
      strcat(String , tmp);
      len = strlen(String);

      /*求字符串的最小表示*/
      minRank = getMin();
      getMinString();
      getNext(minString);
      minTimes = find(minString);

      /*求字符串的最大表示*/
      maxRank = getMax();
      getMaxString();
      getNext(maxString);
      maxTimes = find(maxString);

      /*输出*/
      printf("%d %d %d %d\n" , minRank+1 , minTimes , maxRank+1 , maxTimes);
   }
   return 0;
}