Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package com.company;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- import java.util.NavigableMap;
- import java.util.Scanner;
- import java.util.TreeMap;
- class Node {
- Node() {
- edgeToParent = (char) -1;
- parent = 0;
- suffLink = -1;
- isTerminal = false;
- numbersOfPatternsInVertex = new ArrayList<Integer>();
- trieTransition = new TreeMap<Character, Integer>();
- automatonTransitions = new TreeMap<Character, Integer>();
- }
- Node(int parentNum, Character edgeNum) {
- edgeToParent = edgeNum;
- parent = parentNum;
- suffLink = -1;
- isTerminal = false;
- numbersOfPatternsInVertex = new ArrayList<Integer>();
- trieTransition = new TreeMap<Character, Integer>();
- automatonTransitions = new TreeMap<Character, Integer>();
- }
- NavigableMap<Character, Integer> trieTransition;
- //std::map<char, int> trieTransition;
- NavigableMap<Character, Integer> automatonTransitions;
- ArrayList<Integer> numbersOfPatternsInVertex;
- Character edgeToParent;
- int parent;
- int suffLink;
- boolean isTerminal;
- };
- class Trie {
- ArrayList<Node> trie_;
- ArrayList<Integer> left_submask_position_;
- ArrayList<Integer> right_submask_position_;
- String pattern_;
- ArrayList<Integer> countOfInPatterns;
- Trie(String pattern) {
- trie_ = new ArrayList<Node>();
- left_submask_position_ = new ArrayList<Integer>();
- right_submask_position_ = new ArrayList<Integer>();
- trie_.add(new Node());
- countOfInPatterns = new ArrayList<Integer>();
- buildTrie(pattern);
- }
- void buildTrie(String pattern) {
- pattern_ = pattern;
- searchPositions(pattern);
- for (int i = 0; i < left_submask_position_.size(); i++) {
- addPatternToTrie(left_submask_position_.get(i), right_submask_position_.get(i), i);
- }
- trie_.get(0).suffLink = 0;
- }
- /*
- void step(int i, int vert, int textLen, ArrayList<Integer> countOfInPatterns) {
- for (; vert != 0; vert = getSuffLink(vert)) {
- if (trie_.get(vert).isTerminal) {
- for (int j = 0; j < trie_.get(vert).numbersOfPatternsInVertex.size(); j++) {
- int rightPos = right_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
- int leftPos = left_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
- int inText = i - rightPos + leftPos;
- if ((inText >= leftPos) && (inText - leftPos + pattern_.length() - 1 < textLen)) {
- countOfInPatterns.set(inText - leftPos, countOfInPatterns.get(inText - leftPos) + 1);
- }
- }
- }
- }
- }
- */
- void step(int i, int vert, ArrayList<Integer> countOfInPatterns) {
- for (; vert != 0; vert = getSuffLink(vert)) {
- if (trie_.get(vert).isTerminal) {
- for (int j = 0; j < trie_.get(vert).numbersOfPatternsInVertex.size(); j++) {
- int rightPos = right_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
- int leftPos = left_submask_position_.get(trie_.get(vert).numbersOfPatternsInVertex.get(j));
- int inText = i - rightPos + leftPos;
- //if ((inText >= leftPos) && (inText - leftPos + pattern_.length() - 1 < 10000))
- if ((inText >= leftPos))
- {
- countOfInPatterns.set(inText - leftPos, countOfInPatterns.get(inText - leftPos) + 1);
- }
- }
- }
- }
- }
- /*ArrayList<Integer>*/void searchForSolutions(Character text_i, Integer i, int textlen) {
- //ArrayList<Integer> onFound = new ArrayList<Integer>();
- // int len = text.length();
- // ArrayList<Integer> countOfInPatterns = new ArrayList<Integer>(len);//Arrays.asList(new Integer[len]));
- // for (int i = 0; i < text.length(); ++i)
- countOfInPatterns.add(0);
- //for (int i = 0; i < text.length(); i++) {
- currentVertex = getAutomatonTransition(currentVertex, text_i);
- int vert = currentVertex;
- step(i, vert, /*text.length()*/ countOfInPatterns);
- //}
- //return onFound;
- }
- void getAns(int textLength) {
- for (int i = 0; i < countOfInPatterns.size(); i++) {
- // System.out.println(countOfInPatterns.get(i));
- if (countOfInPatterns.get(i) == left_submask_position_.size() && i + pattern_.length() - 1 <= textLength) {
- System.out.println(i);
- //onFound.add(i);
- }
- }
- }
- int currentVertex = 0;
- //private:
- void searchPositions(String bigPattern) {
- for (int i = 0; i < pattern_.length(); i++) {
- if (bigPattern.charAt(i) != '?') {
- if (i < 1) {
- left_submask_position_.add(i);
- } else if ((bigPattern.charAt(i - 1) == '?')) {
- left_submask_position_.add(i);
- }
- if (i + 1 > pattern_.length() - 1) {
- right_submask_position_.add(i);
- } else if (bigPattern.charAt(i + 1) == '?') {
- right_submask_position_.add(i);
- }
- }
- }
- }
- int getAutomatonTransition(int vert, Character edge) {
- if (!trie_.get(vert).automatonTransitions.containsKey(edge)) {
- if (!trie_.get(vert).trieTransition.containsKey(edge)) {
- if (vert != 0) {
- trie_.get(vert).automatonTransitions.put(edge, getAutomatonTransition(getSuffLink(vert), edge));
- } else {
- trie_.get(vert).automatonTransitions.put(edge, 0);
- }
- } else {
- trie_.get(vert).automatonTransitions.put(edge, trie_.get(vert).trieTransition.get(edge));
- }
- }
- return trie_.get(vert).automatonTransitions.get(edge);
- }
- int getSuffLink(int vert) {
- if (trie_.get(vert).suffLink == -1) {
- if (vert == 0 || trie_.get(vert).parent == 0) {
- trie_.get(vert).suffLink = 0;
- } else {
- trie_.get(vert).suffLink = (Integer) (getAutomatonTransition((getSuffLink(trie_.get(vert).parent)),
- trie_.get(vert).edgeToParent));
- }
- }
- return trie_.get(vert).suffLink;
- }
- void addPatternToTrie(int left, int right, int position) {
- int currentVertex = 0;
- for (int i = left; i <= right; i++) {
- char edge = pattern_.charAt(i);
- if (!trie_.get(currentVertex).trieTransition.containsKey(edge)) {
- Node newNode = new Node(currentVertex, edge);
- trie_.add(newNode);
- Node cur = trie_.get(currentVertex);
- cur.trieTransition.put(edge, trie_.size() - 1);
- trie_.set(currentVertex, cur);
- // trie_.get(currentVertex).trieTransition.get(edge) = trie_.size() - 1;
- }
- currentVertex = trie_.get(currentVertex).trieTransition.get(edge);
- }
- trie_.get(currentVertex).isTerminal = true;
- trie_.get(currentVertex).numbersOfPatternsInVertex.add(position);
- }
- };
- public class Main {
- public static void main(String[] args) throws IOException {
- Scanner scan = new Scanner(System.in);
- int rows = 2;
- ArrayList<String> text = new ArrayList<String>(rows);
- // table.reserve(rows);
- String line;
- line = scan.nextLine();
- System.out.println(line);
- Trie my_trie = new Trie(line);
- char text_i;
- int i = 0;
- int myTextLenght = 0;
- char[] myBud = new char[1];
- int bytes = 0;
- BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
- while ((bytes = in.read(myBud,0,1)) != -1)
- {
- if(myBud[0] == '\n')
- break;
- my_trie.searchForSolutions(myBud[0], i++, 10000);
- myTextLenght++;
- }
- //System.out.println(myTextLenght);
- my_trie.getAns(myTextLenght);
- // while() {
- // System.out.println(a);
- // my_trie.searchForSolutions(a, i, 10000);
- // myTextLenght++;
- // }
- // for(i=0;i<text.get(1).length();++i)
- // {
- // my_trie.searchForSolutions(text.get(1).charAt(i), i, text.get(1).length());
- // }
- //my_trie.getAns(myTextLenght);//++i;
- //ArrayList<Integer> ans = my_trie.searchForSolutions(text.get(1));
- //for (Integer position : ans)
- // System.out.println(position);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement