pku2119 God of the Vile Baskers 字符串的最小表示+hash

題意很簡單
給出一個字符串，求一個最長沒有k模式重復(fù)的前綴
Two strings S1 and S2 are k-identical up to permutation of letters if:

• Both S1 and S2 start and end with an alphabetic character （子串以字母開頭和結(jié)尾）
  
• Both S1 and S2 contain exactly k alphabetic characters （子串包含K個字母）
  
• For each alphabetic character c, the string S1 contains the same number of occurrences of c as the string S2. （子串中各個字母的數(shù)量相等）

這就提示我們可以用字符串的最小表示來做
最簡單的表示法就是"[a的個數(shù)] [b的個數(shù)] ..[z的個數(shù)]"，然后用字符串來hash
貼代碼

 1import java.io.*;
 2import java.util.*;
 3public class Main {
 4
 5    /** *//**
 6     * @param argsarg0
 7     */
 8    static HashSet<String> refer=new HashSet<String>();
 9    static int count[]=new int[26];
10    static String hash()
11    {
12        StringBuffer tmp=new StringBuffer();
13        for(int i=0;i<26;i++)
14            tmp.append(count[i]);
15        return tmp.toString();
16    }
17    public static void main(String[] args) throws IOException{
18        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
19        while(true)
20        {
21            int num=Integer.parseInt(in.readLine());
22            if(num==0) break;
23            refer.clear();
24            String str=in.readLine();
25            Arrays.fill(count, 0);
26            int pos,last=-1,co=0;
27            str=str.toLowerCase();
28            for(++last;last<str.length()&&!Character.isLowerCase(str.charAt(last));last++);
29            for(pos=0;pos<str.length();pos++)
30            {
31                if(Character.isLowerCase(str.charAt(pos)))
32                {
33                    count[str.charAt(pos)-'a']++;
34                    co++;
35                }
36                if(co==num)
37                {
38                    String ha=hash();
39                    if(refer.contains(ha))
40                        break;
41                    else
42                    {
43                        refer.add(ha);
44                        count[str.charAt(last)-'a']--;
45                        for(++last;last<str.length()&&!Character.isLowerCase(str.charAt(last));last++);
46                        co--;
47                    }
48                }
49                
50            }
51            System.out.println(pos);
52                    
53            
54        }
55
56    }
57
58}
59
60

posted on 2010-10-31 00:00 yzhw 閱讀(177) 評論(0)  編輯 收藏 引用 所屬分類: data struct