Package dk.brics.automaton

Class MatchOnlyRunAutomaton

java.lang.Object
dk.brics.automaton.MatchOnlyRunAutomaton
All Implemented Interfaces:
Serializable
public class MatchOnlyRunAutomaton extends Object implements Serializable
Supports an optimised version of substring matching an automaton against an input string in linear time with no backtracking.

In essence we simply take an automaton "mypattern" and match against ".*mypattern". See the docs here from Russ Cox: Link.

As such we do not currently support identifying the start, end position of a match, simply that a match exists.

Execution time is linear to the length of the string O(n) for the method matches(CharSequence) below.

See Also:

  • Constructor Details

    • MatchOnlyRunAutomaton

      public MatchOnlyRunAutomaton(Automaton a)

    • MatchOnlyRunAutomaton

      public MatchOnlyRunAutomaton(Automaton a, boolean tableize)

  • Method Details

    • matches

      public boolean matches(CharSequence input)
      Search the input in linear time based on the size of the input to identify whether this automaton is contained anywhere in the input.

      Has the following constraints:

      1. In the worst case, the execution is equivalent to the length of the input O(n) as we scan the whole input.
      2. There is no backtracking, we simply scan the input char by char until we either match or reach the end.
      3. Method returns immediately if it finds enough chars to complete a match of the pattern.
      4. The method and class has no ability to locate the position of the match, simply that is either exists or not.
      Parameters:
      input - the input to match a substring pattern against
      Returns:
      true if the pattern is found in a substring in the input, or false if the input is not matched. We also return false for null inputs.

    • matches

      public boolean matches(CharSequence input, int pos)
      Search the input in linear time based on the size of the input to identify whether this pattern is contained anywhere in the input from a starting position.

      See matches(CharSequence) for more information.

      This version of the method searches from a specific starting position.

      Parameters:
      input - the input to match a substring pattern against
      pos - the position to start searching from
      Returns:
      true if the pattern is found in a substring in the input, or false if the input is not matched. We also return false for null inputs
      Throws:
      IllegalArgumentException - if the pos is negative or larger than the input length.

    • load

      public static MatchOnlyRunAutomaton load(InputStream stream) throws IOException, ClassCastException, ClassNotFoundException
      Retrieves a serialized MatchOnlyRunAutomaton from a stream.
      Parameters:
      stream - input stream with serialized automaton
      Throws:
      IOException - if input/output related exception occurs
      ClassCastException - if the data is not a serialized MatchOnlyRunAutomaton
      ClassNotFoundException - if the class of the serialized object cannot be found

    • store

      public void store(OutputStream stream) throws IOException
      Writes this MatchOnlyRunAutomaton to the given stream.
      Parameters:
      stream - output stream for serialized automaton
      Throws:
      IOException - if input/output related exception occurs

    • toString

      public String toString()
      Overrides:
      toString in class Object