daily pastebin goal
39%
SHARE
TWEET

Фреквентен стринг [Кол. 2.3]

LonelyShepherd Jan 13th, 2018 (edited) 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  6.  
  7.     K key;
  8.     E value;
  9.  
  10.     public MapEntry (K key, E val) {
  11.         this.key = key;
  12.         this.value = val;
  13.     }
  14.    
  15.     public int compareTo (K that) {
  16.         @SuppressWarnings("unchecked")
  17.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  18.         return this.key.compareTo(other.key);
  19.     }
  20.  
  21.     public String toString () {
  22.         return "(" + key + "," + value + ")";
  23.     }
  24. }
  25.  
  26. class SLLNode<E> {
  27.     protected E element;
  28.     protected SLLNode<E> succ;
  29.  
  30.     public SLLNode(E elem, SLLNode<E> succ) {
  31.         this.element = elem;
  32.         this.succ = succ;
  33.     }
  34.  
  35.     @Override
  36.     public String toString() {
  37.         return element.toString();
  38.     }
  39. }
  40.  
  41. class CBHT<K extends Comparable<K>, E> {
  42.  
  43.     private SLLNode<MapEntry<K,E>>[] buckets;
  44.  
  45.     @SuppressWarnings("unchecked")
  46.     public CBHT(int m) {
  47.         buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  48.     }
  49.  
  50.     private int hash(K key) {
  51.         return Math.abs(key.hashCode()) % buckets.length;
  52.     }
  53.  
  54.     public SLLNode<MapEntry<K,E>> search(K targetKey) {
  55.         int b = hash(targetKey);
  56.         for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  57.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  58.                 return curr;
  59.         }
  60.         return null;
  61.     }
  62.  
  63.     public void insert(K key, E val) {      // Insert the entry <key, val> into this CBHT.
  64.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  65.         int b = hash(key);
  66.         for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  67.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  68.                 curr.element = newEntry;
  69.                 return;
  70.             }
  71.         }
  72.         buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  73.     }
  74.  
  75.     public void delete(K key) {
  76.         int b = hash(key);
  77.         for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  78.             if (key.equals(((MapEntry<K,E>) curr.element).key)) {
  79.                 if (pred == null)
  80.                     buckets[b] = curr.succ;
  81.                 else
  82.                     pred.succ = curr.succ;
  83.                 return;
  84.             }
  85.         }
  86.     }
  87.  
  88.     public String toString() {
  89.         String temp = "";
  90.         for (int i = 0; i < buckets.length; i++) {
  91.             temp += i + ":";
  92.             for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  93.                 temp += curr.element.toString() + " ";
  94.             }
  95.             temp += "\n";
  96.         }
  97.         return temp;
  98.     }
  99.    
  100.     public static String mostOccurent(CBHT<String, Integer> tabela) {
  101.         int max = 0;
  102.         String word = "";
  103.        
  104.         for(int i = 0; i < tabela.buckets.length; i++) {
  105.             SLLNode<MapEntry<String, Integer>> current = tabela.buckets[i];
  106.            
  107.             while(current != null) {
  108.                 if(current.element.value > max) {
  109.                     max = current.element.value;
  110.                     word = current.element.key;
  111.                 } else if(current.element.value == max) {
  112.                     if(current.element.key.length() > word.length()) {
  113.                         max = current.element.value;
  114.                         word = current.element.key;
  115.                     } else if(current.element.key.length() == word.length()) {
  116.                         if(current.element.key.compareTo(word) < 0) {
  117.                             max = current.element.value;
  118.                             word = current.element.key;
  119.                         }
  120.                     }
  121.                 }
  122.                
  123.                 current = current.succ;
  124.             }
  125.         }
  126.        
  127.         return word;
  128.     }
  129.  
  130. }
  131.  
  132. public class MostFrequentSubstring {
  133.     public static void main (String[] args) throws IOException {
  134.         CBHT<String,Integer> tabela = new CBHT<String,Integer>(300);
  135.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  136.        
  137.         String word = br.readLine().trim();
  138.        
  139.         /*
  140.         *
  141.         * Vashiot kod tuka....
  142.         *
  143.         */        
  144.         for(int i = 0; i < word.length(); i++) {
  145.             for(int j = i+1; j <= word.length(); j++) {
  146.                 String substring = word.substring(i, j);
  147.                 SLLNode<MapEntry<String, Integer>> found = tabela.search(substring);
  148.                
  149.                 if(found == null)
  150.                     tabela.insert(substring, 1);
  151.                 else {
  152.                     int occurence = found.element.value;
  153.                     tabela.insert(substring, occurence+1);
  154.                 }
  155.             }
  156.         }
  157.        
  158.         System.out.println(CBHT.mostOccurent(tabela));
  159.     }
  160. }
RAW Paste Data
Top