SHARE
TWEET

Untitled

a guest Oct 15th, 2019 66 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top