Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- public class MaxRepeats {
- FastScanner in;
- PrintWriter out;
- class Answer implements Comparable<Answer> {
- String s;
- int len;
- Answer(String s) {
- this.s = s;
- len = s.length();
- }
- @Override
- public int compareTo(Answer o) {
- return Integer.compare(o.len, len);
- }
- }
- boolean inside(String sub, String in) {
- int len = sub.length();
- for (int st = 0; st < in.length(); st++) {
- if (st + len > in.length())
- continue;
- if (in.substring(st, st + len).equals(sub))
- return true;
- }
- return false;
- }
- ArrayList<String> stupid(String s) {
- ArrayList<String> res = new ArrayList<>();
- int n = s.length();
- for (int st = 0; st < n; st++)
- for (int to = st + 1; to <= n; to++) {
- String substr = s.substring(st, to);
- res.add(substr);
- }
- Collections.sort(res);
- ArrayList<String> repeats = new ArrayList<>();
- for (int i = 1; i < res.size(); i++) {
- String last = repeats.size() == 0 ? "" : repeats
- .get(repeats.size() - 1);
- if (res.get(i).equals(res.get(i - 1)))
- if (!res.get(i).equals(last))
- repeats.add(res.get(i));
- }
- ArrayList<Answer> a1 = new ArrayList<Answer>();
- for (String s2 : repeats)
- a1.add(new Answer(s2));
- Collections.sort(a1);
- ArrayList<String> aa = new ArrayList<>();
- for (Answer a : a1) {
- boolean ok = true;
- for (String alr : aa) {
- if (inside(a.s, alr)) {
- ok = false;
- break;
- }
- }
- if (ok) {
- aa.add(a.s);
- }
- }
- return aa;
- }
- void solve() {
- //String s = "abacaba";
- String s = "abcdabcabcdaabbcaa";
- ArrayList<String> st = stupid(s);
- for (String s2 : st)
- System.err.println(s2);
- }
- void run() {
- try {
- in = new FastScanner(new File("object.in"));
- out = new PrintWriter(new File("object.out"));
- solve();
- out.close();
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- void runIO() {
- in = new FastScanner(System.in);
- out = new PrintWriter(System.out);
- solve();
- out.close();
- }
- class FastScanner {
- BufferedReader br;
- StringTokenizer st;
- public FastScanner(File f) {
- try {
- br = new BufferedReader(new FileReader(f));
- } catch (FileNotFoundException e) {
- e.printStackTrace();
- }
- }
- public FastScanner(InputStream f) {
- br = new BufferedReader(new InputStreamReader(f));
- }
- String next() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return null;
- st = new StringTokenizer(s);
- }
- return st.nextToken();
- }
- boolean hasMoreTokens() {
- while (st == null || !st.hasMoreTokens()) {
- String s = null;
- try {
- s = br.readLine();
- } catch (IOException e) {
- e.printStackTrace();
- }
- if (s == null)
- return false;
- st = new StringTokenizer(s);
- }
- return true;
- }
- int nextInt() {
- return Integer.parseInt(next());
- }
- long nextLong() {
- return Long.parseLong(next());
- }
- }
- public static void main(String[] args) {
- new MaxRepeats().runIO();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment