b'@techreport{GasieniecIndykKrysta96,'b'\nTITLE = {External inverse pattern matching},\nAUTHOR = {Gasieniec, Leszek and Indyk, Piotr and Krysta, Piotr},\nLANGUAGE = {eng},\nNUMBER = {MPI-I-1996-1-030},\nINSTITUTION = {Max-Planck-Institut f{\\"u}r Informatik},\nADDRESS = {Saarbr{\\"u}cken},\nYEAR = {1996},\nDATE = {1996},\nABSTRACT = {We consider {\\sl external inverse pattern matching} problem. Given a text $\\t$ of length $n$ over an ordered alphabet $\\Sigma$, such that $|\\Sigma|=\\sigma$, and a number $m\\le n$. The entire problem is to find a pattern $\\pe\\in \\Sigma^m$ which is not a subword of $\\t$ and which maximizes the sum of Hamming distances between $\\pe$ and all subwords of $\\t$ of length $m$. We present optimal $O(n\\log\\sigma)$-time algorithm for the external inverse pattern matching problem which substantially improves the only known polynomial $O(nm\\log\\sigma)$-time algorithm introduced by Amir, Apostolico and Lewenstein. Moreover we discuss a fast parallel implementation of our algorithm on the CREW PRAM model.},\nTYPE = {Research Report / Max-Planck-Institut f\xc3\xbcr Informatik},\n}\n'