• <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模式重復(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==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 閱讀(177) 評論(0)  編輯 收藏 引用 所屬分類: data struct

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

            導航

            統(tǒng)計

            公告

            統(tǒng)計系統(tǒng)

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            9191精品国产免费久久| 国产农村妇女毛片精品久久| 亚洲一级Av无码毛片久久精品| 久久婷婷五月综合成人D啪| 日韩精品久久久肉伦网站| 国产亚洲婷婷香蕉久久精品| 97超级碰碰碰碰久久久久| 久久久久久久综合狠狠综合| 粉嫩小泬无遮挡久久久久久 | 精品久久久一二三区| 久久亚洲中文字幕精品有坂深雪| 久久91亚洲人成电影网站| 婷婷久久综合九色综合绿巨人| 久久久精品2019免费观看| 亚洲国产精品综合久久网络| 99久久无码一区人妻a黑| 欧美精品福利视频一区二区三区久久久精品 | 精品久久久久久成人AV| 亚洲国产成人久久综合一区77| 丰满少妇人妻久久久久久| 精品伊人久久大线蕉色首页| 久久99精品国产麻豆婷婷| 久久久国产精品福利免费 | 国产精品久久久香蕉| 欧美777精品久久久久网| 久久久国产精品亚洲一区| 久久精品国产亚洲av麻豆蜜芽| 99热都是精品久久久久久| 国产午夜久久影院| 日韩AV无码久久一区二区| 无码国内精品久久人妻| 偷偷做久久久久网站| 久久这里的只有是精品23| 久久久久久亚洲精品无码| 香蕉久久一区二区不卡无毒影院| 成人国内精品久久久久影院| 午夜欧美精品久久久久久久| 国产偷久久久精品专区| 日本欧美久久久久免费播放网 | 久久精品亚洲一区二区三区浴池 | 亚洲国产美女精品久久久久∴ |