We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
More or less quite ugly implemented aho corasic + kmp for this case looks like this:
mind that I assumed all words in pattern are the same length and ommited some unnecessary code for implementing subpatterns in aho.
Also the time complexity is O(R*C*DELTA + r*c*DELTA) where DELTA is size of dictionary (possible next letters) so in this case [0-9]
private static class Node {
public Map<Character, Node> nextNode;
public Node failure;
int terminal;
public Node() {
nextNode = new HashMap<>();
for(char c = '0'; c <= '9'; ++c) {
nextNode.put(c, null);
}
failure = null;
terminal = -1;
}
public Node addWord(String word, int index) {
Node q = this;
for(int i = 0; i < word.length(); ++i) {
char x = word.charAt(i);
q.nextNode.putIfAbsent(x, new Node());
q = q.nextNode.get(x);
}
if(q.terminal == -1) {
q.terminal = index;
}
return this;
}
public List<Node> computeBFS() {
ArrayList<Node> result = new ArrayList();
Queue<Node> queue = new LinkedList<>();
this.nextNode.entrySet().forEach(entry -> {
if(entry.getValue() != null) {
queue.add(entry.getValue());
}
});
while(!queue.isEmpty()) {
Node q = queue.remove();
result.add(q);
q.nextNode.entrySet().forEach(entry -> {
if(entry.getValue() != null) {
queue.add(entry.getValue());
}
});
}
return result;
}
public void createFailureFallback() {
List<Node> bfsOrder = computeBFS();
this.failure = this;
for(char c = '0'; c <= '9'; ++c) {
if(this.nextNode.get(c) != null) {
this.nextNode.get(c).failure = this;
}
}
for(char c = '0'; c <= '9'; ++c) {
this.nextNode.putIfAbsent(c, this);
}
bfsOrder.forEach(
node -> {
for(char c = '0'; c <= '9'; ++c) {
Node x = node.nextNode.get(c);
if(x == null) {
node.nextNode.put(c, node.failure.nextNode.get(c));
} else {
x.failure = node.failure.nextNode.get(c);
}
}
}
);
}
}
static int [] computeKMPLookup(int [] pattern) {
int [] lookup = new int[pattern.length];
lookup[0] = -1;
int k = -1;
for(int q = 1; q < pattern.length; ++q) {
while(k > -1 && pattern[k+1] != pattern[q]) {
k = lookup[k];
}
if(pattern[k+1] == pattern[q]) {
++k;
}
lookup[q] = k;
}
return lookup;
}
static String gridSearch(String[] G, String[] P) {
Node head = new Node();
for(int i = 0; i < P.length; ++i) {
head.addWord(P[i], i);
}
head.createFailureFallback();
//match array will have information about which row from pattern matches at which point in searched string
int [][]match = new int[G.length][];
for(int i = 0; i < match.length; ++i) {
match[i] = new int[G[i].length()];
Node q = head;
for(int j = 0; j < G[i].length(); ++j) {
q = q.nextNode.get(G[i].charAt(j));
match[i][j] = q.terminal;
if(q.terminal != -1) {
if(q.failure!= null) {
q = q.failure;
}
}
}
}
//we need to find pattern that we will search in columns of amtch arrays, it might be that some of rows of pattern are repeated
int [] pattern = new int[P.length];
for(int i = 0; i < P.length; ++i) {
Node q = head;
for(int j = 0; j < P[i].length(); ++j) {
q = q.nextNode.get(P[i].charAt(j));
if(q.terminal != -1) {
pattern[i] = q.terminal;
q = q.failure;
}
}
}
//compute KMP lookup array
int[] lookup = computeKMPLookup(pattern);
//now we jsut use KMP to search for the pattern
for(int column = 0; column < match[0].length; ++column) {
int q = -1;
for(int i = 0; i < match.length; ++i) {
while(q > -1 && pattern[q+1] != match[i][column]) {
q = lookup[q];
}
if(pattern[q+1] == match[i][column]) {
++q;
}
if(q == pattern.length - 1) {
return "YES";
}
}
}
return "NO";
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Grid Search
You are viewing a single comment's thread. Return to all comments →
More or less quite ugly implemented aho corasic + kmp for this case looks like this: mind that I assumed all words in pattern are the same length and ommited some unnecessary code for implementing subpatterns in aho. Also the time complexity is O(R*C*DELTA + r*c*DELTA) where DELTA is size of dictionary (possible next letters) so in this case [0-9]