学步园

http://acm.hdu.edu.cn/showproblem.php?pid=2609

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

struct Node{
 char str[110];
};
Node nodes[10010];

bool com(Node &a,Node &b){
 return (strcmp(a.str,b.str)<0);
}

int minexp(char *str){
 int len=strlen(str);
 int i=0,j=1,k=0;
 while(i<len&&j<len&&k<len){
  int t=str[(i+k)%len]-str[(j+k)%len];
  if(t>0){
   i=i+k+1,k=0;
  }else if(t<0){
   j=j+k+1,k=0;
  }else{
   k++;
  }
  if(i==j){
   j++,k=0;
  }
 }
 return i<j?i:j;
}


int main(){
 //freopen("a.txt","r",stdin);
 int number;
 while(scanf("%d",&number)!=EOF){
  int i;
  char now[200];
  for(i=1;i<=number;i++){
   scanf("%s",now);
   int len=strlen(now);
   int where=minexp(now);
   int j,t;
   for(t=0,j=where;j<len;j++,t++){
    nodes[i].str[t]=now[j];
   }
   for(j=0;j<where;j++,t++){
    nodes[i].str[t]=now[j];
   }
   nodes[i].str[t]='\0';
  }
  sort(&nodes[1],&nodes[number+1],com);
  int out=1;
  for(i=2;i<=number;i++){
   if(strcmp(nodes[i-1].str,nodes[i].str)!=0){
    out++;
   }
  }
  printf("%d\n",out);
 }
 return 0;
}

以下为我的超时Java代码，未优化，待下次有时间再研究！

/*
2011-9-18
author:BearFly1990
*/
package acm.hdu.tests;

import java.io.BufferedInputStream;
import java.util.Scanner;

public class HDU_2609 {
    private static  StringBuilder[] sb = new StringBuilder[10001];
    private static StringBuilder[] neck = new StringBuilder[100001];
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        while(in.hasNext()){
            int n = in.nextInt();
            for(int i = 0; i < n; i++){
                sb[i] = new StringBuilder(in.next());
            }
            int result = check(n);
            System.out.println(result);
        }
    }
    private static int check(int n) {
        neck[0]= sb[0];
        int length = sb[0].length();
        int ans = 1;
   NEXT:for(int i = 1; i < n ; i++){
            for(int j = 0; j < length; j++){
                StringBuilder temp = sb[i].append(sb[i]
                      .charAt(0)).deleteCharAt(0);
                for(int k = 0; k < ans; k++){
                    //System.out.println("temp:"+temp);
                    //System.out.println("neck:"+neck[k]);
                    if(temp.toString().equals(neck[k].toString())){
                        continue NEXT;
                    }
                }
            }
            neck[ans++] = sb[i];
        }
        return ans;
    }
    
}