001package algs13;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac MultiwordSearch.java
005 *  Execution:    java MultiwordSearch query1 query2 ... < input.txt
006 *  Dependencies: Queue.java StdIn.java
007 *
008 *  Find the shortest interval (number of words) in the input file
009 *  that contains the query words in the order specified on the command line.
010 *
011 *************************************************************************/
012
013public class XMultiwordSearch {
014        public static void main(String[] args) {
015                String[] words = StdIn.readAll().split("\\s+");
016
017                // construct queues[j] = sequence of positions of jth query word
018                @SuppressWarnings("unchecked")
019                final
020                Queue<Integer>[] queues = new Queue[args.length];
021                for (int j = 0; j < args.length; j++) {
022                        queues[j] = new Queue<>();
023                }
024                for (int i = 0; i < words.length; i++) {
025                        for (int j = 0; j < args.length; j++) {
026                                if (words[i].equals(args[j])) queues[j].enqueue(i);
027                        }
028                }
029
030                // repeatedly find smallest interval starting at position of queues[0]
031                boolean done = false;
032                int bestlo = -1, besthi = words.length;
033                while (!queues[0].isEmpty()) {
034                        int lo = queues[0].dequeue();
035                        int hi = lo;
036                        for (int j = 1; j < args.length; j++) {
037                                while (!queues[j].isEmpty() && queues[j].peek() <= hi) {
038                                        queues[j].dequeue();
039                                }
040                                if (queues[j].isEmpty())  { done = true; break; }
041                                else hi = queues[j].peek();
042                        }
043                        if (!done && hi - lo < besthi - bestlo) {
044                                besthi = hi;
045                                bestlo = lo;
046                        }
047
048                }
049
050                if (bestlo >= 0) {
051                        for (int i = bestlo; i <= besthi; i++)
052                                StdOut.print(words[i] + " ");
053                        StdOut.println();
054                }
055                else
056                        StdOut.println("NOT FOUND");
057        }
058}
059