Advertisement
since85stas

Untitled

Jun 4th, 2021
451
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.65 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class CaseB {
  5.  
  6.     public static void main(String[] args) throws IOException {
  7.         BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream(new File("input4.txt"))));
  8.         StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
  9.         String s = tokenizer.nextToken();
  10.  
  11.         StringTokenizer tokenizerStr = new StringTokenizer(reader.readLine());
  12.         int n = Integer.parseInt(tokenizerStr.nextToken());
  13.  
  14.         Trie trie = new Trie();
  15.  
  16.         for (int i = 0; i < n; i++) {
  17.             tokenizer = new StringTokenizer(reader.readLine());
  18.             trie.put(tokenizer.nextToken());
  19.         }
  20.  
  21.         List<Integer> result = new ArrayList<>();
  22.  
  23.         trie.checkWord(s, 0, result);
  24.  
  25.         // если в результат ничего не добавили значит разбить нельзя
  26.         if (result.size() == 0) System.out.println("NO");
  27.         else System.out.println("YES");
  28.  
  29.     }
  30.  
  31.  
  32.     static class Trie {
  33.  
  34.         private static class Node {
  35.             //            private Integer value;
  36.             private Node[] next = new Node[R];
  37.             boolean isEnd;
  38.         }
  39.  
  40.         private static final int R = 26;
  41.         private Node root = new Node();
  42.  
  43.         public void put(String key) {
  44.             root = put(root, key, 0);
  45.         }
  46.  
  47.         private Node put(Node x, String key, int d) {
  48.             if (x == null) x = new Node();
  49.             if (d == key.length()) {
  50.                 x.isEnd = true;
  51.                 return x;
  52.             }
  53.             char c = key.charAt(d);
  54.             x.next[c - 'a'] = put(x.next[c - 'a'], key, d + 1);
  55.             return x;
  56.         }
  57.  
  58.         public boolean checkWord(String word, int index, List<Integer> result) {
  59.             if (result.size() > 0) return true;
  60.             Node curr = root;
  61.  
  62.             for (int i = index; i < word.length(); i++) {
  63.                 if (curr.next[word.charAt(i) - 'a'] == null)
  64.                     return false;
  65.                 if (curr.next[word.charAt(i) - 'a'].isEnd) {
  66.                     if (i == word.length() - 1) {
  67.                         // если доходим до конца слова и оно присутствует то результат есть
  68.                         result.add((index));
  69.                         return true;
  70.                     }
  71.                     checkWord(word, i + 1, result);
  72.                 }
  73.                 if (result.size() > 0) return true;
  74.                 curr = curr.next[word.charAt(i) - 'a'];
  75.             }
  76.             return false;
  77.         }
  78.  
  79.  
  80.     }
  81.  
  82.  
  83. }
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement