Kame3

Проверка на спелување - [хеширање]

Jan 16th, 2021 (edited)
871
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Проверка на спелување Problem 5 (0 / 0)
  2.  
  3. Потребно е да се направи проверка на текст даден на англиски, дали е во ред напишан (односно дали правилно се напишани зборовите). За таа цел прво се даваат речник на зборови (односно листа на зборови кои ги содржи англискиот јазик), а потоа се дава текст. Како резултат треба да се испечатат сите зборови кои се направилно напишани или ги нема во речникот.
  4.  
  5. Влез: Прво се дава број N на поими кои ќе ги содржи речникот, а во наредните N реда се дадени зборовите кои ги содржи англискиот јазик. Потоа се дава еден текст, кој треба да се провери дали е правилно напишан.
  6.  
  7. Излез: Се печати листа на зборови кои се неправилно напишани (секој во посебен ред). Доколку сите зборови се добро напишани се печати: Bravo.
  8.  
  9. Забелешка: Треба да се игнорираат интерпункциск знаци како точка (.), запирка (,), извичник (!) и прашалник (?). Исто така да се внимава на голема и мала буква, односно иако зборовите во речникот се со мали букви, во реченица може да појават со голема почетна буква и притоа се сметаат за точни. Работете со хеш табела со отворени кофички. Сами треба да го одредите бројот на кофички и хеш функцијата.
  10.  
  11. Име на класа (Java): Speluvanje.
  12.  
  13.  
  14. import java.io.BufferedReader;
  15. import java.io.IOException;
  16. import java.io.InputStreamReader;
  17.  
  18. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  19.     K key;
  20.     E value;
  21.  
  22.     public MapEntry (K key, E val) {
  23.         this.key = key;
  24.         this.value = val;
  25.     }
  26.     public int compareTo (K that) {
  27.         @SuppressWarnings("unchecked")
  28.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  29.         return this.key.compareTo(other.key);
  30.     }
  31.     public String toString () {
  32.         return "(" + key + "," + value + ")";
  33.     }
  34. }
  35.  
  36.  
  37. class OBHT<K extends Comparable<K>,E> {
  38.  
  39.     private MapEntry<K,E>[] buckets;
  40.     static final int NONE = -1; // ... distinct from any bucket index.
  41.     @SuppressWarnings({ "rawtypes", "unchecked" })
  42.     private static final MapEntry former = new MapEntry(null, null);
  43.     private int occupancy = 0;
  44.    
  45.     @SuppressWarnings("unchecked")
  46.     public OBHT (int m) {
  47.         buckets = (MapEntry<K,E>[]) new MapEntry[m];
  48.     }
  49.  
  50.     private int hash (K key) {
  51.         return Math.abs(key.hashCode()) % buckets.length;
  52.     }
  53.    
  54.     public MapEntry<K,E> getBucket(int i){
  55.         return buckets[i];
  56.     }
  57.    
  58.     public int search (K targetKey) {
  59.         int b = hash(targetKey); int n_search=0;
  60.         for (;;) {
  61.             MapEntry<K,E> oldEntry = buckets[b];
  62.             if (oldEntry == null)
  63.                 return NONE;
  64.             else if (targetKey.equals(oldEntry.key))
  65.                 return b;
  66.             else{
  67.                 b = (b + 1) % buckets.length;
  68.                 n_search++;
  69.                 if(n_search==buckets.length)
  70.                     return NONE;
  71.             }
  72.         }
  73.     }
  74.  
  75.     public void insert (K key, E val) {
  76.         MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  77.         int b = hash(key); int n_search=0;
  78.        
  79.         for (;;) {
  80.             MapEntry<K,E> oldEntry = buckets[b];
  81.             if (oldEntry == null) {
  82.                 if (++occupancy == buckets.length) {
  83.                     System.out.println("Hash tabelata e polna!!!");
  84.                 }
  85.                 buckets[b] = newEntry;
  86.                 return;
  87.             } else if (oldEntry == former
  88.                     || key.equals(oldEntry.key)) {
  89.                 buckets[b] = newEntry;
  90.                 return;
  91.             } else{
  92.                 b = (b + 1) % buckets.length;
  93.                 n_search++;
  94.                 if(n_search==buckets.length)
  95.                     return;
  96.  
  97.             }
  98.         }
  99.     }
  100.    
  101.     @SuppressWarnings("unchecked")
  102.     public void delete (K key) {
  103.         int b = hash(key); int n_search=0;
  104.         for (;;) {
  105.             MapEntry<K,E> oldEntry = buckets[b];
  106.            
  107.             if (oldEntry == null)
  108.                 return;
  109.             else if (key.equals(oldEntry.key)) {
  110.                 buckets[b] = former;
  111.                 return;
  112.             } else{
  113.                 b = (b + 1) % buckets.length;
  114.                 n_search++;
  115.                 if(n_search==buckets.length)
  116.                     return;
  117.  
  118.             }
  119.         }
  120.     }
  121.  
  122.     public String toString () {
  123.         String temp = "";
  124.         for (int i = 0; i < buckets.length; i++) {
  125.             temp += i + ":";
  126.             if (buckets[i] == null)
  127.                 temp += "\n";
  128.             else if (buckets[i] == former)
  129.                 temp += "former\n";
  130.             else
  131.                 temp += buckets[i] + "\n";
  132.         }
  133.         return temp;
  134.     }
  135. }
  136.  
  137.  
  138. class Zbor implements Comparable<Zbor>{
  139.     String zbor;
  140.  
  141.     public Zbor(String zbor) {
  142.         this.zbor = zbor.toLowerCase();
  143.     }
  144.     @Override
  145.     public boolean equals(Object obj) {
  146.         Zbor pom = (Zbor) obj;
  147.         return this.zbor.equals(pom.zbor);
  148.     }
  149.     @Override
  150.     public int hashCode() {
  151.         return zbor.hashCode();
  152.     }
  153.     @Override
  154.     public String toString() {
  155.         return zbor;
  156.     }
  157.     @Override
  158.     public int compareTo(Zbor arg0) {
  159.         return zbor.compareTo(arg0.zbor);
  160.     }
  161. }
  162.  
  163. public class Main {
  164.     public static void main(String[] args) throws IOException {
  165.         OBHT<Zbor, String> tabela;
  166.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  167.         int N = Integer.parseInt(br.readLine());
  168.         //---Vie odluchete za goleminata na hesh tabelata----
  169.         tabela = new OBHT<Zbor,String>(2*N-1);
  170.        
  171.         for (int i=0; i< N; ++i) {
  172.             String word = br.readLine();
  173.             Zbor zbor = new Zbor(word);
  174.             tabela.insert(zbor, word);
  175.         }
  176.        
  177.         String line = br.readLine();
  178.         String parts[] = line.split(" ");
  179.         boolean flag = true;
  180.         for (int i=0; i < parts.length; ++i) {
  181.             String word = parts[i];
  182.             if (!Character.isLetter(word.charAt(word.length()-1)))
  183.                 word = word.substring(0,word.length()-1);
  184.             if (word.length() == 0)
  185.                 continue;
  186.             Zbor zbor = new Zbor(word);
  187.             if (tabela.search(zbor) == -1){
  188.                 System.out.println(word);
  189.                 flag = false;
  190.             }
  191.         }
  192.         if (flag)
  193.             System.out.println("Bravo");
  194.     }
  195. }
  196.  
  197.  
  198.  
  199. Sample input
  200.  
  201. 4
  202. where
  203. is
  204. my
  205. cat
  206. Where is my cat?
  207.  
  208. Sample output
  209.  
  210. Bravo
  211.  
  212.  
RAW Paste Data