metalni

APS 2. Kolokvium Exercises Proverka na speluvanje

Jan 19th, 2021
815
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.     K key;
  7.     E value;
  8.  
  9.     public MapEntry (K key, E val) {
  10.         this.key = key;
  11.         this.value = val;
  12.     }
  13.     public int compareTo (K that) {
  14.         @SuppressWarnings("unchecked")
  15.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  16.         return this.key.compareTo(other.key);
  17.     }
  18.     public String toString () {
  19.         return "(" + key + "," + value + ")";
  20.     }
  21. }
  22.  
  23.  
  24. class OBHT<K extends Comparable<K>,E> {
  25.  
  26.     private MapEntry<K,E>[] buckets;
  27.     static final int NONE = -1; // ... distinct from any bucket index.
  28.     @SuppressWarnings({ "rawtypes", "unchecked" })
  29.     private static final MapEntry former = new MapEntry(null, null);
  30.     private int occupancy = 0;
  31.  
  32.     @SuppressWarnings("unchecked")
  33.     public OBHT (int m) {
  34.         buckets = (MapEntry<K,E>[]) new MapEntry[m];
  35.     }
  36.  
  37.     private int hash (K key) {
  38.         return Math.abs(key.hashCode()) % buckets.length;
  39.     }
  40.  
  41.     public MapEntry<K,E> getBucket(int i){
  42.         return buckets[i];
  43.     }
  44.  
  45.     public int search (K targetKey) {
  46.         int b = hash(targetKey); int n_search=0;
  47.         for (;;) {
  48.             MapEntry<K,E> oldEntry = buckets[b];
  49.             if (oldEntry == null)
  50.                 return NONE;
  51.             else if (targetKey.equals(oldEntry.key))
  52.                 return b;
  53.             else{
  54.                 b = (b + 1) % buckets.length;
  55.                 n_search++;
  56.                 if(n_search==buckets.length)
  57.                     return NONE;
  58.             }
  59.         }
  60.     }
  61.  
  62.     public void insert (K key, E val) {
  63.         MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  64.         int b = hash(key); int n_search=0;
  65.  
  66.         for (;;) {
  67.             MapEntry<K,E> oldEntry = buckets[b];
  68.             if (oldEntry == null) {
  69.                 if (++occupancy == buckets.length) {
  70.                     System.out.println("Hash tabelata e polna!!!");
  71.                 }
  72.                 buckets[b] = newEntry;
  73.                 return;
  74.             } else if (oldEntry == former
  75.                     || key.equals(oldEntry.key)) {
  76.                 buckets[b] = newEntry;
  77.                 return;
  78.             } else{
  79.                 b = (b + 1) % buckets.length;
  80.                 n_search++;
  81.                 if(n_search==buckets.length)
  82.                     return;
  83.  
  84.             }
  85.         }
  86.     }
  87.  
  88.     @SuppressWarnings("unchecked")
  89.     public void delete (K key) {
  90.         int b = hash(key); int n_search=0;
  91.         for (;;) {
  92.             MapEntry<K,E> oldEntry = buckets[b];
  93.  
  94.             if (oldEntry == null)
  95.                 return;
  96.             else if (key.equals(oldEntry.key)) {
  97.                 buckets[b] = former;
  98.                 return;
  99.             } else{
  100.                 b = (b + 1) % buckets.length;
  101.                 n_search++;
  102.                 if(n_search==buckets.length)
  103.                     return;
  104.  
  105.             }
  106.         }
  107.     }
  108.  
  109.     public String toString () {
  110.         String temp = "";
  111.         for (int i = 0; i < buckets.length; i++) {
  112.             temp += i + ":";
  113.             if (buckets[i] == null)
  114.                 temp += "\n";
  115.             else if (buckets[i] == former)
  116.                 temp += "former\n";
  117.             else
  118.                 temp += buckets[i] + "\n";
  119.         }
  120.         return temp;
  121.     }
  122. }
  123.  
  124.  
  125. class Zbor implements Comparable<Zbor>{
  126.     String zbor;
  127.  
  128.     public Zbor(String zbor) {
  129.         this.zbor = zbor;
  130.     }
  131.     @Override
  132.     public boolean equals(Object obj) {
  133.         Zbor pom = (Zbor) obj;
  134.         return this.zbor.equals(pom.zbor);
  135.     }
  136.     @Override
  137.     public int hashCode() {
  138.         /*
  139.          *
  140.          * Vie ja kreirate hesh funkcijata
  141.          *
  142.          */
  143.         return zbor.hashCode();
  144.     }
  145.     @Override
  146.     public String toString() {
  147.         return zbor;
  148.     }
  149.     @Override
  150.     public int compareTo(Zbor arg0) {
  151.         return zbor.compareTo(arg0.zbor);
  152.     }
  153. }
  154.  
  155. public class Speluvanje {
  156.     public static void main(String[] args) throws IOException {
  157.         OBHT<Zbor, String> tabela;
  158.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  159.         int N = Integer.parseInt(br.readLine());
  160.         //---Vie odluchete za goleminata na hesh tabelata----
  161.         tabela = new OBHT<Zbor,String>(300);
  162.  
  163.         /*
  164.          *
  165.          * Vashiot kod tuka....
  166.          *
  167.          */
  168.  
  169.         Zbor zbor;
  170.         String temp;
  171.         for(int i=0; i<N; i++){
  172.             temp = br.readLine();
  173.             zbor = new Zbor(temp);
  174.             tabela.insert(zbor, temp);
  175.         }
  176.  
  177.         String word;
  178.         String text = br.readLine();
  179.         String [] split = text.split(" ");
  180.         boolean flag = true;
  181.         for(int i=0; i<split.length; i++){
  182.             char znak = split[i].charAt(split[i].length()-1);
  183.             word = split[i];
  184.             if(!Character.isAlphabetic(znak))
  185.                 word = word.substring(0, word.length()-1);
  186.             word = word.toLowerCase();
  187.  
  188.             if (word.length() == 0)
  189.                 continue;
  190.  
  191.             Zbor searchWord = new Zbor(word);
  192.             if(tabela.search(searchWord) == -1) {
  193.                 System.out.println(word);
  194.                 flag = false;
  195.             }
  196.         }
  197.         if(flag)
  198.             System.out.println("Bravo");
  199.     }
  200. }
  201.  
RAW Paste Data