• <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年10月>
            262728293012
            3456789
            10111213141516
            17181920212223
            24252627282930
            31123456

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            成人久久精品一区二区三区| 亚洲Av无码国产情品久久| 色8久久人人97超碰香蕉987| 亚洲AV成人无码久久精品老人| 久久精品人人做人人爽电影蜜月| 成人久久综合网| 日韩精品无码久久一区二区三| 久久亚洲AV成人无码软件| 国产成人久久精品一区二区三区| 国产农村妇女毛片精品久久| 久久成人小视频| 国产高清国内精品福利99久久| 2019久久久高清456| 久久久青草青青亚洲国产免观| 亚洲а∨天堂久久精品9966| 国内精品久久久久影院一蜜桃| 久久亚洲国产精品五月天婷| 丰满少妇高潮惨叫久久久| 亚洲国产小视频精品久久久三级 | 日本免费久久久久久久网站| 精品国产青草久久久久福利| 亚洲精品蜜桃久久久久久| 亚洲一级Av无码毛片久久精品| 久久国产免费观看精品| 久久中文骚妇内射| 国产成人久久精品一区二区三区| 色噜噜狠狠先锋影音久久| 国产精品综合久久第一页| 久久久久久无码Av成人影院| 无码AV波多野结衣久久| 欧美一区二区三区久久综合| 久久午夜电影网| 久久777国产线看观看精品| 99久久亚洲综合精品网站| 亚洲人AV永久一区二区三区久久| 久久这里只有精品18| 青青久久精品国产免费看| 狼狼综合久久久久综合网| 久久人人爽人爽人人爽av| 久久久亚洲欧洲日产国码二区 | 久久久久九国产精品|