Latkoski

Фреквентен стринг

Jan 26th, 2016
237
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.07 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.lang.annotation.Target;
  5. import java.lang.ref.PhantomReference;
  6. import java.text.StringCharacterIterator;
  7. import java.util.Map;
  8.  
  9. import javax.management.openmbean.OpenDataException;
  10. import javax.swing.InputMap;
  11. import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
  12. import javax.swing.plaf.basic.BasicTabbedPaneUI.TabbedPaneLayout;
  13. import javax.swing.text.StyledEditorKit.ForegroundAction;
  14.  
  15. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  16.  
  17.     // Each MapEntry object is a pair consisting of a key (a Comparable
  18.     // object) and a value (an arbitrary object).
  19.     K key;
  20.     E value;
  21.  
  22.     public MapEntry (K key, E val) {
  23.         this.key = key;
  24.         this.value = val;
  25.     }
  26.    
  27.     public int compareTo (K that) {
  28.     // Compare this map entry to that map entry.
  29.         @SuppressWarnings("unchecked")
  30.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  31.         return this.key.compareTo(other.key);
  32.     }
  33.  
  34.     public String toString () {
  35.         return "<" + key + "," + value + ">";
  36.     }
  37. }
  38. class SLLNode<E> {
  39.     protected E element;
  40.     protected SLLNode<E> succ;
  41.  
  42.     public SLLNode(E elem, SLLNode<E> succ) {
  43.         this.element = elem;
  44.         this.succ = succ;
  45.     }
  46.  
  47.     @Override
  48.     public String toString() {
  49.         return element.toString();
  50.     }
  51. }
  52.  
  53. class CBHT<K extends Comparable<K>, E> {
  54.  
  55.     // An object of class CBHT is a closed-bucket hash table, containing
  56.     // entries of class MapEntry.
  57.     private SLLNode<MapEntry<K,E>>[] buckets;
  58.  
  59.     @SuppressWarnings("unchecked")
  60.     public CBHT(int m) {
  61.         // Construct an empty CBHT with m buckets.
  62.         buckets = (SLLNode<MapEntry<K,E>>[]) new SLLNode[m];
  63.     }
  64.  
  65.     private int hash(K key) {
  66.         // Translate key to an index of the array buckets.
  67.         return Math.abs(key.hashCode()) % buckets.length;
  68.     }
  69.  
  70.     public SLLNode<MapEntry<K,E>> search(K targetKey) {
  71.         // Find which if any node of this CBHT contains an entry whose key is
  72.         // equal
  73.         // to targetKey. Return a link to that node (or null if there is none).
  74.         int b = hash(targetKey);
  75.         for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  76.             if (targetKey.equals(((MapEntry<K, E>) curr.element).key))
  77.                 return curr;
  78.         }
  79.         return null;
  80.     }
  81.  
  82.     public void insert(K key, E val) {      // Insert the entry <key, val> into this CBHT.
  83.         MapEntry<K, E> newEntry = new MapEntry<K, E>(key, val);
  84.         int b = hash(key);
  85.         for (SLLNode<MapEntry<K,E>> curr = buckets[b]; curr != null; curr = curr.succ) {
  86.             if (key.equals(((MapEntry<K, E>) curr.element).key)) {
  87.                 // Make newEntry replace the existing entry ...
  88.                 curr.element = newEntry;
  89.                 return;
  90.             }
  91.         }
  92.         // Insert newEntry at the front of the 1WLL in bucket b ...
  93.         buckets[b] = new SLLNode<MapEntry<K,E>>(newEntry, buckets[b]);
  94.     }
  95.  
  96.     public void delete(K key) {
  97.         // Delete the entry (if any) whose key is equal to key from this CBHT.
  98.         int b = hash(key);
  99.         for (SLLNode<MapEntry<K,E>> pred = null, curr = buckets[b]; curr != null; pred = curr, curr = curr.succ) {
  100.             if (key.equals(((MapEntry<K,E>) curr.element).key)) {
  101.                 if (pred == null)
  102.                     buckets[b] = curr.succ;
  103.                 else
  104.                     pred.succ = curr.succ;
  105.                 return;
  106.             }
  107.         }
  108.     }
  109.  
  110.     public String toString() {
  111.         String temp = "";
  112.         for (int i = 0; i < buckets.length; i++) {
  113.             temp += i + ":";
  114.             for (SLLNode<MapEntry<K,E>> curr = buckets[i]; curr != null; curr = curr.succ) {
  115.                 temp += curr.element.toString() + " ";
  116.             }
  117.             temp += "\n";
  118.         }
  119.         return temp;
  120.     }
  121. }
  122. public class MostFrequentSubstring {
  123.     public static void main(String[] args) throws NumberFormatException, IOException
  124.     {
  125.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  126.         CBHT<String,Integer> table = new CBHT<String,Integer>(200);
  127.         String stringce = br.readLine().trim();
  128.         int brojac = 0;
  129.         for(int i=0;i<stringce.length();i++)
  130.         {
  131.             for(int j=i;j<=stringce.length();j++)
  132.             {
  133.                 SLLNode<MapEntry<String,Integer>> node=table.search(stringce.substring(i,j));
  134.                 if(node == null)
  135.                 {
  136.                     table.insert(stringce.substring(i,j),1);
  137.                 }
  138.                 else{
  139.                     brojac = node.element.value+1;
  140.                     table.insert(stringce.substring(i,j), brojac);
  141.                 }
  142.             }
  143.         }
  144.         //System.out.println(table);
  145.         String najdolga="";
  146.         int maxi = Integer.MIN_VALUE;
  147.         for(int i=0;i<stringce.length();i++)
  148.         {
  149.             for(int j=i;j<=stringce.length();j++)
  150.             {
  151.                 SLLNode<MapEntry<String,Integer>> node2 = table.search(stringce.substring(i,j));
  152.                 if(stringce.substring(i,j).equals(""))
  153.                 {
  154.                     continue;
  155.                 }
  156.                 if(node2.element.value > maxi)
  157.                 {
  158.                     maxi = node2.element.value;
  159.                     najdolga = node2.element.key;
  160.                 }
  161.                 if(node2.element.value == maxi)
  162.                 {
  163.                     if(node2.element.key.length() > najdolga.length())
  164.                     {
  165.                         najdolga = node2.element.key;
  166.                     }
  167.                     if(node2.element.key.length()==najdolga.length())
  168.                     {
  169.                         if(node2.element.key.compareTo(najdolga)<0)
  170.                         {
  171.                                 najdolga=node2.element.key;                                
  172.                         }
  173.                     }
  174.                 }
  175.             }
  176.         }
  177.         System.out.println(najdolga);
  178.     }
  179. }
Advertisement
Add Comment
Please, Sign In to add comment