題意大概是給出一個(gè)字符串，要求求出長(zhǎng)度范圍在[a,b]區(qū)間內(nèi)最大頻率子串
看到這道題，我第一反應(yīng)是后綴數(shù)組。。。結(jié)果悲劇的TLE了。。后來(lái)觀察到時(shí)01串，然后就想到了位壓縮，下次做題一定要注意，關(guān)注題目的特殊性。。
1 import java.io.*;
2 import java.util.*;
3 public class Main {
4
5 /**
6 * @param args
7 */
8 static class cmp implements Comparator<String>
9 {
10 public int compare(String a,String b)
11 {
12 if(a.length()!=b.length())
13 return b.length()-a.length();
14 else
15 return b.compareTo(a);
16 }
17 }
18 public static void main(String[] args) throws IOException {
19 BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
20 TreeMap<Integer,ArrayList<String> > refer=new TreeMap<Integer,ArrayList<String> >(Collections.reverseOrder());
21 HashMap<Integer,Integer> trefer=new HashMap<Integer,Integer>();
22 int a=Integer.parseInt(in.readLine());
23 int b=Integer.parseInt(in.readLine());
24 int n=Integer.parseInt(in.readLine());
25 String str=in.readLine();
26 for(int len=a;len<=b;len++)
27 {
28 if(len>str.length()-1) continue;
29 int pos=0;
30 int tmp=0;
31 for(pos=0;pos<len;pos++)
32 tmp=(tmp<<1)|(str.charAt(pos)=='1'?1:0);
33 trefer.clear();
34 trefer.put(tmp, 1);
35 for(pos=len;pos<str.length()-1;pos++)
36 {
37 tmp=((tmp<<1)&((1<<len)-1))|(str.charAt(pos)=='1'?1:0);
38 if(trefer.containsKey(tmp))
39 trefer.put(tmp, trefer.get(tmp)+1);
40 else
41 trefer.put(tmp, 1);
42 }
43 for(Map.Entry<Integer, Integer> p:trefer.entrySet())
44 {
45 String tstr=Integer.toBinaryString(p.getKey());
46 while(tstr.length()<len) tstr='0'+tstr;
47 if(refer.containsKey(p.getValue()))
48 refer.get(p.getValue()).add(tstr);
49 else
50 {
51 ArrayList<String> ttt=new ArrayList<String>();
52 ttt.add(tstr);
53 refer.put(p.getValue(), ttt);
54 }
55
56 }
57 while(refer.size()>n) refer.remove(refer.lastKey());
58 }
59 while(refer.size()>n) refer.remove(refer.lastKey());
60 for(Map.Entry<Integer,ArrayList<String> >p:refer.entrySet())
61 {
62 Collections.sort(p.getValue(),new cmp());
63 System.out.print(p.getKey());
64 for(String i:p.getValue())
65 System.out.print(" "+i);
66 System.out.println();
67
68 }
69
70 }
71
72 }
73