qwerty787788

temp

Mar 12th, 2013
221
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.18 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class MaxRepeats {
  5.     FastScanner in;
  6.     PrintWriter out;
  7.  
  8.     class Answer implements Comparable<Answer> {
  9.         String s;
  10.         int len;
  11.  
  12.         Answer(String s) {
  13.             this.s = s;
  14.             len = s.length();
  15.         }
  16.  
  17.         @Override
  18.         public int compareTo(Answer o) {
  19.             return Integer.compare(o.len, len);
  20.         }
  21.     }
  22.  
  23.     boolean inside(String sub, String in) {
  24.         int len = sub.length();
  25.         for (int st = 0; st < in.length(); st++) {
  26.             if (st + len > in.length())
  27.                 continue;
  28.             if (in.substring(st, st + len).equals(sub))
  29.                 return true;
  30.         }
  31.         return false;
  32.     }
  33.  
  34.     ArrayList<String> stupid(String s) {
  35.         ArrayList<String> res = new ArrayList<>();
  36.         int n = s.length();
  37.         for (int st = 0; st < n; st++)
  38.             for (int to = st + 1; to <= n; to++) {
  39.                 String substr = s.substring(st, to);
  40.                 res.add(substr);
  41.             }
  42.         Collections.sort(res);
  43.         ArrayList<String> repeats = new ArrayList<>();
  44.         for (int i = 1; i < res.size(); i++) {
  45.             String last = repeats.size() == 0 ? "" : repeats
  46.                     .get(repeats.size() - 1);
  47.             if (res.get(i).equals(res.get(i - 1)))
  48.                 if (!res.get(i).equals(last))
  49.                     repeats.add(res.get(i));
  50.         }
  51.         ArrayList<Answer> a1 = new ArrayList<Answer>();
  52.         for (String s2 : repeats)
  53.             a1.add(new Answer(s2));
  54.         Collections.sort(a1);
  55.         ArrayList<String> aa = new ArrayList<>();
  56.         for (Answer a : a1) {
  57.             boolean ok = true;
  58.             for (String alr : aa) {
  59.                 if (inside(a.s, alr)) {
  60.                     ok = false;
  61.                     break;
  62.                 }
  63.             }
  64.             if (ok) {
  65.                 aa.add(a.s);
  66.             }
  67.         }
  68.         return aa;
  69.     }
  70.  
  71.     void solve() {
  72.         //String s = "abacaba";
  73.         String s = "abcdabcabcdaabbcaa";
  74.         ArrayList<String> st = stupid(s);
  75.         for (String s2 : st)
  76.             System.err.println(s2);
  77.     }
  78.  
  79.     void run() {
  80.         try {
  81.             in = new FastScanner(new File("object.in"));
  82.             out = new PrintWriter(new File("object.out"));
  83.  
  84.             solve();
  85.  
  86.             out.close();
  87.         } catch (FileNotFoundException e) {
  88.             e.printStackTrace();
  89.         }
  90.     }
  91.  
  92.     void runIO() {
  93.  
  94.         in = new FastScanner(System.in);
  95.         out = new PrintWriter(System.out);
  96.  
  97.         solve();
  98.  
  99.         out.close();
  100.     }
  101.  
  102.     class FastScanner {
  103.         BufferedReader br;
  104.         StringTokenizer st;
  105.  
  106.         public FastScanner(File f) {
  107.             try {
  108.                 br = new BufferedReader(new FileReader(f));
  109.             } catch (FileNotFoundException e) {
  110.                 e.printStackTrace();
  111.             }
  112.         }
  113.  
  114.         public FastScanner(InputStream f) {
  115.             br = new BufferedReader(new InputStreamReader(f));
  116.         }
  117.  
  118.         String next() {
  119.             while (st == null || !st.hasMoreTokens()) {
  120.                 String s = null;
  121.                 try {
  122.                     s = br.readLine();
  123.                 } catch (IOException e) {
  124.                     e.printStackTrace();
  125.                 }
  126.                 if (s == null)
  127.                     return null;
  128.                 st = new StringTokenizer(s);
  129.             }
  130.             return st.nextToken();
  131.         }
  132.  
  133.         boolean hasMoreTokens() {
  134.             while (st == null || !st.hasMoreTokens()) {
  135.                 String s = null;
  136.                 try {
  137.                     s = br.readLine();
  138.                 } catch (IOException e) {
  139.                     e.printStackTrace();
  140.                 }
  141.                 if (s == null)
  142.                     return false;
  143.                 st = new StringTokenizer(s);
  144.             }
  145.             return true;
  146.         }
  147.  
  148.         int nextInt() {
  149.             return Integer.parseInt(next());
  150.         }
  151.  
  152.         long nextLong() {
  153.             return Long.parseLong(next());
  154.         }
  155.     }
  156.  
  157.     public static void main(String[] args) {
  158.         new MaxRepeats().runIO();
  159.     }
  160. }
Advertisement
Add Comment
Please, Sign In to add comment