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

题意很简单
给出一个字符串,求一个最长没有k模式重复的前缀
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 (子串以字母开头和结尾)
  • 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. (子串中各个字母的数量相等)

这就提示我们可以用字符串的最小表示来做
最简单的表示法就是"[a的个数] [b的个数] ..[z的个数]",然后用字符串来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==0break;
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 阅读(171) 评论(0)  编辑 收藏 引用 所属分类: data struct


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

公告

统计系统

留言簿(1)

随笔分类(227)

文章分类(2)

OJ

最新随笔

搜索

积分与排名

最新评论

阅读排行榜