duplicityyy

[АПС] - Фреквентен стринг

Jan 18th, 2021
1,119
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Фреквентен стринг Problem 3 (0 / 3)
  2. Даден е стринг. Треба да се најде најчестиот под-стринг кој е дел од него и да се испечати. Доколку два под-стринга се исто фреквентни, тогаш се печати подолгиот. Доколку и овој услов го исполнуваат тогаш се печати лексикографски помалиот.
  3.  
  4. Пример: За стрингот "abc" под-стрингови се "a", "b", "c", "ab", "bc", "abc". Сите имаат иста честота па затоа се печати најдолгиот "abc".
  5.  
  6. Име на класата (Java): MostFrequentSubstring.
  7.  
  8. Sample Input
  9. lopatlopatlopatlopat
  10. Sample Output
  11. lopat
  12.  
  13. Sample Input
  14. bomasdfsbomlkbomlfklfbomlzxzxzbomdalksjfkslbom
  15. Sample Output
  16. bom
  17.  
  18. Sample Input
  19. asdfalkjsdhfkljasncjkznkjdansdkjfnlk
  20. Sample Output
  21. k
  22.  
  23. SampleInput
  24. uuuuaaaabbbb
  25. SampleOutput
  26. a
  27.  
  28. _______________________________________________________________________________________________________________________________________
  29.  
  30. import java.io.BufferedReader;
  31. import java.io.IOException;
  32. import java.io.InputStreamReader;
  33.  
  34. class MapEntry<K extends Comparable<K>, E> implements Comparable<K> {
  35.  
  36.     K key;
  37.     E value;
  38.  
  39.     public MapEntry(K key, E val) {
  40.         this.key = key;
  41.         this.value = val;
  42.     }
  43.  
  44.     public int compareTo(K that) {
  45.         @SuppressWarnings("unchecked")
  46.         MapEntry<K, E> other = (MapEntry<K, E>) that;
  47.         return this.key.compareTo(other.key);
  48.     }
  49.  
  50.     public String toString() {
  51.         return "(" + key + "," + value + ")";
  52.     }
  53. }
  54.  
  55. class SLLNode<E> {
  56.     protected E element;
  57.     protected SLLNode<E> succ;
  58.  
  59.     public SLLNode(E elem, SLLNode<E> succ) {
  60.         this.element = elem;
  61.         this.succ = succ;
  62.     }
  63.  
  64.     @Override
  65.     public String toString() {
  66.         return element.toString();
  67.     }
  68. }
  69.  
  70. class CBHT<K extends Comparable<K>, E> {
  71.  
  72.     private SLLNode<MapEntry<K, E>>[] buckets;
  73.  
  74.     @SuppressWarnings("unchecked")
  75.     public CBHT(int m) {
  76.         buckets = (SLLNode<MapEntry<K, E>>[]) new SLLNode[m];
  77.     }
  78.  
  79.     private int hash(K key) {
  80.         return Math.abs(key.hashCode()) % buckets.length;
  81.     }
  82.  
  83.     public SLLNode<MapEntry<K, E>> search(K targetKey) {
  84.         int b = hash(targetKey);
  85.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  86.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  87.                 return curr;
  88.         }
  89.         return null;
  90.     }
  91.  
  92.     public void insert(K key, E val) { // Insert the entry <key, val> into this CBHT.
  93.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  94.         int b = hash(key);
  95.         for (SLLNode<MapEntry<K, E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  96.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  97.                 curr.element = newEntry;
  98.                 return;
  99.             }
  100.         }
  101.         buckets[b] = new SLLNode<MapEntry<K, E>>(newEntry, buckets[b]);
  102.     }
  103.  
  104.     public void delete(K key) {
  105.         int b = hash(key);
  106.         for (SLLNode<MapEntry<K, E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  107.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  108.                 if (pred == null)
  109.                     buckets[b] = curr.succ;
  110.                 else
  111.                     pred.succ = curr.succ;
  112.                 return;
  113.             }
  114.         }
  115.     }
  116.  
  117.     public String toString() {
  118.         String temp = "";
  119.         for (int i = 0; i < buckets.length; i++) {
  120.             temp += i + ":";
  121.             for (SLLNode<MapEntry<K, E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  122.                 temp += curr.element.toString() + " ";
  123.             }
  124.             temp += "\n";
  125.         }
  126.         return temp;
  127.     }
  128.  
  129. }
  130.  
  131. class Values {
  132.     public int frequency;
  133.     public int lexico;
  134.     public int length;
  135.  
  136.     public Values(int frequency, int lexico, int length) {
  137.         this.frequency = frequency;
  138.         this.lexico = lexico;
  139.         this.length = length;
  140.     }
  141.  
  142. }
  143. public class MostFrequentSubstring {
  144.  
  145.     public static int leksikografska(String s) {
  146.         int n = 0;
  147.         for (int i = 0; i < s.length(); i++) {
  148.             n += s.charAt(i);
  149.         }
  150.         return n;
  151.     }
  152.  
  153.     public static int minLexico(CBHT<String, Values> cbht, String s) {
  154.         SLLNode<MapEntry<String, Values>> node;
  155.         String zbor;
  156.         int min = 100000;
  157.         for (int i = 0; i < s.length(); i++) {
  158.             for (int j = i + 1; j <= s.length(); j++) {
  159.                 zbor = s.substring(i, j);
  160.                 node = cbht.search(zbor);
  161.                 if(node != null) {
  162.                     if (node.element.value.lexico < min)
  163.                         min = node.element.value.lexico;
  164.                 }
  165.             }
  166.         }
  167.  
  168.         // System.out.println(max);
  169.         return min;
  170.     }
  171.  
  172.     public static int maxLength(CBHT<String, Values> cbht, String s) {
  173.         SLLNode<MapEntry<String, Values>> node;
  174.         String zbor;
  175.         int max = 0;
  176.         for (int i = 0; i < s.length(); i++) {
  177.             for (int j = i + 1; j <= s.length(); j++) {
  178.                 zbor = s.substring(i, j);
  179.                 node = cbht.search(zbor);
  180.                 if(node != null) {
  181.                     if (node.element.value.length > max)
  182.                         max = node.element.value.length;
  183.                 }
  184.             }
  185.         }
  186.  
  187.         // System.out.println(max);
  188.         return max;
  189.     }
  190.  
  191.     /**
  192.      *
  193.      * @param cbht
  194.      * @param s
  195.      * @return
  196.      */
  197.     public static int maxFrequency(CBHT<String, Values> cbht, String s) {
  198.         SLLNode<MapEntry<String, Values>> node;
  199.         String zbor;
  200.         int max = 0;
  201.         for (int i = 0; i < s.length(); i++) {
  202.             for (int j = i + 1; j <= s.length(); j++) {
  203.                 zbor = s.substring(i, j);
  204.                 node = cbht.search(zbor);
  205.                 if(node != null) {
  206.                     if (node.element.value.frequency > max)
  207.                         max = node.element.value.frequency;
  208.                 }
  209.             }
  210.         }
  211.  
  212.         // System.out.println(max);
  213.         return max;
  214.     }
  215.  
  216.     /**
  217.      *
  218.      * @param cbht
  219.      * @param s
  220.      * @return
  221.      */
  222.     public static String najdi(CBHT<String, Values> cbht, String s) {
  223.         SLLNode<MapEntry<String, Values>> node;
  224.         String zbor;
  225.         for (int i = 0; i < s.length(); i++) {
  226.             for (int j = i + 1; j <= s.length(); j++) {
  227.                 zbor = s.substring(i, j);
  228.                 node = cbht.search(zbor);
  229.                 // System.out.println(node.element.key + " " + node.element.value.frequency + "
  230.                 // " + node.element.value.lexico);
  231.             }
  232.         }
  233.         //System.out.println(kopija.toString());
  234.  
  235.  
  236.  
  237.         // brishi substrings shto se pomali od najfrekfentnite
  238.         int maxFrequency = maxFrequency(cbht, s);
  239.         for (int i = 0; i < s.length(); i++) {
  240.             for (int j = i + 1; j <= s.length(); j++) {
  241.                 zbor = s.substring(i, j);
  242.                 node = cbht.search(zbor);
  243.                 if(node != null) {
  244.                     if (node.element.value.frequency < maxFrequency) {
  245.                         //System.out.println(node.element.key + " " + node.element.value.frequency + " " + node.element.value.length + " " + node.element.value.lexico);
  246.                         cbht.delete(node.element.key);
  247.                     }
  248.                 }
  249.             }
  250.         }
  251.  
  252.         //brishi substrings pomali od najgolemiot
  253.         int maxLength = maxLength(cbht, s);
  254.         for (int i = 0; i < s.length(); i++) {
  255.             for (int j = i + 1; j <= s.length(); j++) {
  256.                 zbor = s.substring(i, j);
  257.                 node = cbht.search(zbor);
  258.                 if(node != null) {
  259.                     if (node.element.value.length < maxLength) {
  260.                         //System.out.println(node.element.key + " " + node.element.value.frequency + " " + node.element.value.length + " " + node.element.value.lexico);
  261.                         cbht.delete(node.element.key);
  262.                     }
  263.                 }
  264.             }
  265.         }
  266.  
  267.         //brishi pogolemi leksikografski
  268.         int minLexico = minLexico(cbht, s);
  269.         for (int i = 0; i < s.length(); i++) {
  270.             for (int j = i + 1; j <= s.length(); j++) {
  271.                 zbor = s.substring(i, j);
  272.                 node = cbht.search(zbor);
  273.                 if(node != null) {
  274.                     if (node.element.value.lexico > minLexico) {
  275.                         //System.out.println(node.element.key + " " + node.element.value.frequency + " " + node.element.value.length + " " + node.element.value.lexico);
  276.                         cbht.delete(node.element.key);
  277.                     }
  278.                 }
  279.             }
  280.         }
  281.  
  282.         //najdi go zborot vo hashtabelata
  283.         String finalWord = "";
  284.         for (int i = 0; i < s.length(); i++) {
  285.             for (int j = i + 1; j <= s.length(); j++) {
  286.                 zbor = s.substring(i, j);
  287.                 node = cbht.search(zbor);
  288.                 if(node != null) {
  289.                     if (node.element.key.equals(zbor)) {
  290.                         //System.out.println(node.element.key + " " + node.element.value.frequency + " " + node.element.value.length + " " + node.element.value.lexico);
  291.                         finalWord = node.element.key;
  292.                     }
  293.                 }
  294.             }
  295.         }
  296.  
  297.         return finalWord;
  298.     }
  299.  
  300.     public static void main(String[] args) throws IOException {
  301.         CBHT<String, Values> tabela = new CBHT<String, Values>(300);
  302.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  303.  
  304.         String word = br.readLine().trim();
  305.  
  306.         // vnesuvanje vo tabela
  307.         for (int i = 0; i < word.length(); i++) {
  308.             for (int j = i + 1; j <= word.length(); j++) {
  309.                 String zbor = word.substring(i, j);
  310.                 Values v = new Values(1, leksikografska(zbor), zbor.length());
  311.                 SLLNode<MapEntry<String, Values>> node = tabela.search(zbor);
  312.                 if (node == null) {
  313.                     tabela.insert(zbor, v);
  314.                 } else {
  315.                     node.element.value.frequency++;
  316.                 }
  317.             }
  318.         }
  319.         //System.out.println(tabela.toString());
  320.         // System.out.println(maxFrequency(tabela, word));
  321.         //System.out.println(minLexico(tabela, word));
  322.         System.out.println(najdi(tabela, word));
  323.     }
  324. }
  325.  
RAW Paste Data