Guest User

Untitled

a guest
Oct 15th, 2019
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.company;
  2.  
  3. import java.io.BufferedReader;
  4. import java.io.IOException;
  5. import java.io.InputStreamReader;
  6. import java.util.ArrayList;
  7. import java.util.NavigableMap;
  8. import java.util.Scanner;
  9. import java.util.TreeMap;
  10.  
  11. class Node {
  12.  
  13. Node() {
  14. edgeToParent = (char) -1;
  15. parent = 0;
  16. suffLink = -1;
  17. isTerminal = false;
  18. numbersOfPatternsInVertex = new ArrayList<Integer>();
  19. trieTransition = new TreeMap<Character, Integer>();
  20. automatonTransitions = new TreeMap<Character, Integer>();
  21. }
  22.  
  23. Node(int parentNum, Character edgeNum) {
  24. edgeToParent = edgeNum;
  25. parent = parentNum;
  26. suffLink = -1;
  27. isTerminal = false;
  28. numbersOfPatternsInVertex = new ArrayList<Integer>();
  29. trieTransition = new TreeMap<Character, Integer>();
  30. automatonTransitions = new TreeMap<Character, Integer>();
  31. }
  32.  
  33.  
  34. NavigableMap<Character, Integer> trieTransition;
  35. //std::map<char, int> trieTransition;
  36. NavigableMap<Character, Integer> automatonTransitions;
  37. ArrayList<Integer> numbersOfPatternsInVertex;
  38. Character edgeToParent;
  39. int parent;
  40. int suffLink;
  41. boolean isTerminal;
  42. };
  43.  
  44. class Trie {
  45.  
  46. ArrayList<Node> trie_;
  47. ArrayList<Integer> left_submask_position_;
  48. ArrayList<Integer> right_submask_position_;
  49. String pattern_;
  50. ArrayList<Integer> countOfInPatterns;
  51.  
  52. Trie(String pattern) {
  53. trie_ = new ArrayList<Node>();
  54. left_submask_position_ = new ArrayList<Integer>();
  55. right_submask_position_ = new ArrayList<Integer>();
  56. trie_.add(new Node());
  57. countOfInPatterns = new ArrayList<Integer>();
  58.  
  59. buildTrie(pattern);
  60. }
  61.  
  62. void buildTrie(String pattern) {
  63. pattern_ = pattern;
  64. searchPositions(pattern);
  65. for (int i = 0; i < left_submask_position_.size(); i++) {
  66. addPatternToTrie(left_submask_position_.get(i), right_submask_position_.get(i), i);
  67. }
  68. trie_.get(0).suffLink = 0;
  69. }
  70.  
  71. /*
  72. void step(int i, int vert, int textLen, ArrayList<Integer> countOfInPatterns) {
  73. for (; vert != 0; vert = getSuffLink(vert)) {
  74. if (trie_.get(vert).isTerminal) {
  75. for (int j = 0; j < trie_.get(vert).numbersOfPatternsInVertex.size(); j++) {
  76. int rightPos = right_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
  77. int leftPos = left_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
  78. int inText = i - rightPos + leftPos;
  79.  
  80. if ((inText >= leftPos) && (inText - leftPos + pattern_.length() - 1 < textLen)) {
  81. countOfInPatterns.set(inText - leftPos, countOfInPatterns.get(inText - leftPos) + 1);
  82. }
  83. }
  84. }
  85. }
  86. }
  87. */
  88. void step(int i, int vert, ArrayList<Integer> countOfInPatterns) {
  89. for (; vert != 0; vert = getSuffLink(vert)) {
  90. if (trie_.get(vert).isTerminal) {
  91. for (int j = 0; j < trie_.get(vert).numbersOfPatternsInVertex.size(); j++) {
  92. int rightPos = right_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
  93. int leftPos = left_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
  94. int inText = i - rightPos + leftPos;
  95.  
  96. //if ((inText >= leftPos) && (inText - leftPos + pattern_.length() - 1 < 10000))
  97. if ((inText >= leftPos))
  98. {
  99. countOfInPatterns.set(inText - leftPos, countOfInPatterns.get(inText - leftPos) + 1);
  100. }
  101. }
  102. }
  103. }
  104. }
  105.  
  106. /*ArrayList<Integer>*/void searchForSolutions(Character text_i, Integer i, int textlen) {
  107. //ArrayList<Integer> onFound = new ArrayList<Integer>();
  108. // int len = text.length();
  109. // ArrayList<Integer> countOfInPatterns = new ArrayList<Integer>(len);//Arrays.asList(new Integer[len]));
  110. // for (int i = 0; i < text.length(); ++i)
  111. countOfInPatterns.add(0);
  112. //for (int i = 0; i < text.length(); i++) {
  113. currentVertex = getAutomatonTransition(currentVertex, text_i);
  114. int vert = currentVertex;
  115. step(i, vert, /*text.length()*/ countOfInPatterns);
  116. //}
  117. //return onFound;
  118. }
  119.  
  120. void getAns(int textLength) {
  121. for (int i = 0; i < countOfInPatterns.size(); i++) {
  122. // System.out.println(countOfInPatterns.get(i));
  123. if (countOfInPatterns.get(i) == left_submask_position_.size() && i + pattern_.length() - 1 <= textLength) {
  124. System.out.println(i);
  125. //onFound.add(i);
  126. }
  127. }
  128. }
  129.  
  130. int currentVertex = 0;
  131. //private:
  132.  
  133. void searchPositions(String bigPattern) {
  134. for (int i = 0; i < pattern_.length(); i++) {
  135. if (bigPattern.charAt(i) != '?') {
  136. if (i < 1) {
  137. left_submask_position_.add(i);
  138. } else if ((bigPattern.charAt(i - 1) == '?')) {
  139. left_submask_position_.add(i);
  140. }
  141. if (i + 1 > pattern_.length() - 1) {
  142. right_submask_position_.add(i);
  143. } else if (bigPattern.charAt(i + 1) == '?') {
  144. right_submask_position_.add(i);
  145. }
  146. }
  147. }
  148. }
  149.  
  150. int getAutomatonTransition(int vert, Character edge) {
  151. if (!trie_.get(vert).automatonTransitions.containsKey(edge)) {
  152. if (!trie_.get(vert).trieTransition.containsKey(edge)) {
  153. if (vert != 0) {
  154. trie_.get(vert).automatonTransitions.put(edge, getAutomatonTransition(getSuffLink(vert), edge));
  155. } else {
  156. trie_.get(vert).automatonTransitions.put(edge, 0);
  157. }
  158. } else {
  159. trie_.get(vert).automatonTransitions.put(edge, trie_.get(vert).trieTransition.get(edge));
  160. }
  161. }
  162. return trie_.get(vert).automatonTransitions.get(edge);
  163. }
  164.  
  165. int getSuffLink(int vert) {
  166. if (trie_.get(vert).suffLink == -1) {
  167. if (vert == 0 || trie_.get(vert).parent == 0) {
  168. trie_.get(vert).suffLink = 0;
  169. } else {
  170. trie_.get(vert).suffLink = (Integer) (getAutomatonTransition((getSuffLink(trie_.get(vert).parent)),
  171. trie_.get(vert).edgeToParent));
  172. }
  173. }
  174. return trie_.get(vert).suffLink;
  175. }
  176.  
  177. void addPatternToTrie(int left, int right, int position) {
  178. int currentVertex = 0;
  179. for (int i = left; i <= right; i++) {
  180. char edge = pattern_.charAt(i);
  181. if (!trie_.get(currentVertex).trieTransition.containsKey(edge)) {
  182. Node newNode = new Node(currentVertex, edge);
  183. trie_.add(newNode);
  184. Node cur = trie_.get(currentVertex);
  185. cur.trieTransition.put(edge, trie_.size() - 1);
  186. trie_.set(currentVertex, cur);
  187. // trie_.get(currentVertex).trieTransition.get(edge) = trie_.size() - 1;
  188. }
  189. currentVertex = trie_.get(currentVertex).trieTransition.get(edge);
  190. }
  191. trie_.get(currentVertex).isTerminal = true;
  192. trie_.get(currentVertex).numbersOfPatternsInVertex.add(position);
  193. }
  194. };
  195.  
  196. public class Main {
  197.  
  198. public static void main(String[] args) throws IOException {
  199. Scanner scan = new Scanner(System.in);
  200. int rows = 2;
  201. ArrayList<String> text = new ArrayList<String>(rows);
  202. // table.reserve(rows);
  203. String line;
  204. line = scan.nextLine();
  205. System.out.println(line);
  206. Trie my_trie = new Trie(line);
  207. char text_i;
  208. int i = 0;
  209. int myTextLenght = 0;
  210. char[] myBud = new char[1];
  211. int bytes = 0;
  212. BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
  213. while ((bytes = in.read(myBud,0,1)) != -1)
  214. {
  215. if(myBud[0] == '\n')
  216. break;
  217. my_trie.searchForSolutions(myBud[0], i++, 10000);
  218. myTextLenght++;
  219. }
  220. //System.out.println(myTextLenght);
  221. my_trie.getAns(myTextLenght);
  222. // while() {
  223. // System.out.println(a);
  224. // my_trie.searchForSolutions(a, i, 10000);
  225. // myTextLenght++;
  226. // }
  227.  
  228. // for(i=0;i<text.get(1).length();++i)
  229. // {
  230. // my_trie.searchForSolutions(text.get(1).charAt(i), i, text.get(1).length());
  231. // }
  232. //my_trie.getAns(myTextLenght);//++i;
  233. //ArrayList<Integer> ans = my_trie.searchForSolutions(text.get(1));
  234. //for (Integer position : ans)
  235. // System.out.println(position);
  236.  
  237. }
  238. }
RAW Paste Data