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