• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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 閱讀(174) 評論(0)  編輯 收藏 引用 所屬分類: data struct

            <2010年12月>
            2829301234
            567891011
            12131415161718
            19202122232425
            2627282930311
            2345678

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            一本一本久久A久久综合精品| 久久精品成人国产午夜| 怡红院日本一道日本久久| 久久精品天天中文字幕人妻| 免费国产99久久久香蕉| 日本久久中文字幕| 一本色综合网久久| 精品免费久久久久国产一区| 久久精品国产99国产精品亚洲| 97久久精品无码一区二区天美 | 久久国产香蕉一区精品| 亚洲乱码精品久久久久..| 久久噜噜久久久精品66| 国产精品久久久久影院嫩草| 波多野结衣久久精品| 97久久精品人人做人人爽| 一本一本久久A久久综合精品| 久久免费大片| 99久久精品免费| 久久青青草原综合伊人| 麻豆亚洲AV永久无码精品久久| 色婷婷久久综合中文久久一本| 久久综合九色综合97_久久久| 伊人久久无码中文字幕| 亚洲国产一成久久精品国产成人综合| 国产精品福利一区二区久久| 久久亚洲精品成人AV| 丁香色欲久久久久久综合网| 中文精品99久久国产| 久久无码国产| 综合久久给合久久狠狠狠97色 | 久久久久久国产精品美女| 久久精品国产精品亚洲精品| 99久久久国产精品免费无卡顿| 久久亚洲精精品中文字幕| 久久精品中文闷骚内射| 欧美一区二区三区久久综| 久久99热只有频精品8| 69SEX久久精品国产麻豆| 97久久香蕉国产线看观看| 久久香蕉国产线看观看99|