4

Given a string S and a list L of patterns [L1, ..., Ln], how would you find the list of all tokens in S matching a pattern in L and so that the total number of matched letters in S is maximized?

A dummy example would be S = "thenuke", L = {"the", "then", "nuke"} and we would like to retrieve ["the", "nuke"] as if we start by matching "then", we do not get the solution maximizing the total number of letters in S being matched.

I have been looking at other SO questions, string matching algorithms but found nothing to efficiently solve the maximization part of the problem. This must have been studied e.g. in bioinformatics but I'm not in the field so any help (including link to academic papers) deeply appreciated!

1
  • Keeping a counter for every try, then find the best match? Like run it for the, if you can find nuke, return a 2, run it for then and return 1 so instantly check if 1 is larger which obviously isn't and keep the previous which is the max... And keep doing until you are done! Sep 11, 2012 at 20:18

2 Answers 2

2

This can be solved in O(|S| + |L| + k) time, where k is the total number of matches of all strings from L in S. There are two major steps:

  1. Run Aho-Corasick. This will give you all matches of any string from L in S. This runs in the same time as mentioned above.

  2. Initialize an array, A, of integers of length |S| + 1 to all zeros. March through the array, at position i set A[i] to A[i-1] if it is larger, then for every match, M, from L in S at position i, set A[i+|M|] to the max of A[i+|M|] and A[i] + |M|.

Here is some code, in Go, that does exactly this. It uses a package I wrote that has a convenient wrapper for calling Aho-Corasick.

package main

import (
  "fmt"
  "github.com/runningwild/stringz"
)

func main() {
  input := []byte("thenuke")
  patterns := [][]byte{[]byte("hen"), []byte("thenu"), []byte("uke")}

  // This runs Aho-Corasick on the input string and patterns, it returns a
  // map, matches, such that matches[i] is a list of indices into input where
  // patterns[i] matches the input string.  The running time of this is
  // O(|input| + |patterns| + k) and uses O(|patterns| + k) auxillary storage,
  // where k is the total number of matches found.
  find := stringz.FindSet(patterns)
  matches := find.In(input)

  // We want to invert the map so that it maps from index to all strings that
  // match at that index.
  at_pos := make([][]int, len(input)+1)
  for index, hits := range matches {
    for _, hit := range hits {
      at_pos[hit] = append(at_pos[hit], index)
    }
  }

  // Now we do a single pass through the string, at every position we will
  // keep track of how many characters in the input string we can match up to
  // that point.
  max := make([]int, len(input)+1)
  for i := range max {
    // If this position isn't as good as the previous position, then we'll use
    // the previous position.  It just means that there is a character that we
    // were unable to match anything to.
    if i > 0 && max[i-1] > max[i] {
      max[i] = max[i-1]
    }

    // Look through any string that matches at this position, if its length is
    // L, then L positions later in the string we can have matched L more
    // character if we use this string now.  This might mean that we don't use
    // another string that earlier we thought we'd be matching right now, we'll
    // find out later which one was better.
    for _, hit := range at_pos[i] {
      L := len(patterns[hit])
      if i+L < len(max) && max[i+L] < max[i]+L {
        max[i+L] = max[i] + L
      }
    }
  }

  fmt.Printf("%v\n", max)
}
1
  • +1. I wrote a Python implementation of this algorithm in this answer. Sep 13, 2012 at 11:19
1

You can solve this in time O(|L||S|) by dynamic programming: build up iteratively a table giving the best match for each initial substring of S = s1s2...sn:

  • B(0), the best match for the zero-length initial substring of S, is the empty match.

  • Suppose we have already computed the best match, B(i), for each i < k, and we want now to compute B(k). Let p be a pattern in L, with length |p|, and let j = k − |p| + 1. If p = sj...sk then there is a match for s1s2...sk that consists of B(j) followed by p. Let B(k) be the best such match found after considering all the patterns in L.

  • B(n) is the best match for the whole of S.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.