Download code

Jump to: navigation, search

Back to Finite_automaton_string_search_algorithm_(Java)

Download for Windows: single file, zip

Download for UNIX: single file, zip, tar.gz, tar.bz2

DFAStringSearch.java

  1 /* The authors of this work have released all rights to it and placed it
  2 in the public domain under the Creative Commons CC0 1.0 waiver
  3 (http://creativecommons.org/publicdomain/zero/1.0/).
  4 
  5 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  6 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  7 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
  8 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
  9 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 10 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 11 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 12 
 13 Retrieved from: http://en.literateprograms.org/Finite_automaton_string_search_algorithm_(Java)?oldid=14960
 14 */
 15 
 16 import java.util.BitSet;
 17 
 18 import java.util.Map;
 19 import java.util.HashMap;
 20 import java.util.List;
 21 import java.util.ArrayList;
 22 
 23 class State<E>
 24 {
 25     private static int nextStateNum = 0;
 26     private final int num = nextStateNum++;
 27     public final BitSet positions;
 28     public final Map<E,State<E>> transitions = new HashMap<E,State<E>>();
 29     public boolean finale;
 30 
 31 
 32     public State(BitSet bs) { positions = bs; }
 33     public String toString() { return Integer.toString(num); }
 34 }
 35 
 36 public class DFAStringSearch<E>
 37 {
 38     // maps the set of string positions a state represents to the state
 39     private final Map<BitSet, State<E>> stateMap = new HashMap<BitSet, State<E>>();
 40     // list of states in order of creation
 41     private final List<State<E>> states = new ArrayList<State<E>>();
 42 
 43     public State<E> initialState;
 44 
 45     public DFAStringSearch(E[] pattern)
 46     {
 47         BitSet initialPos = new BitSet();
 48 	initialPos.set(0);
 49 	initialState = getState(initialPos);
 50         for (int i = 0; i < states.size(); i++)
 51         {
 52             State<E> s = states.get(i);
 53             for (int j = s.positions.nextSetBit(0); j >= 0; j = s.positions.nextSetBit(j+1))
 54             {
 55                 if (j == pattern.length)
 56 		{
 57 		    s.finale = true;
 58 		    break;
 59 		}
 60                 E cNext = pattern[j];
 61                 if (!s.transitions.containsKey(cNext))
 62                     fillTransitionTableEntry(pattern, s, cNext);
 63             }
 64         }
 65     }
 66     public State<E> getState(BitSet s)
 67     {
 68         if (stateMap.containsKey(s))
 69             return stateMap.get(s);
 70         else
 71         {
 72             State<E> st = new State<E>(s);
 73             stateMap.put(s, st);
 74             states.add(st);
 75             return st;
 76         }
 77     }
 78     private void fillTransitionTableEntry(E[] pattern, State<E> s, E cNext)
 79     {
 80         BitSet newPositions = new BitSet();
 81         newPositions.set(0);
 82         for (int i = s.positions.nextSetBit(0); i >= 0 && i < pattern.length; i = s.positions.nextSetBit(i+1))
 83         {
 84             if (pattern[i].equals(cNext))
 85                 newPositions.set(i + 1);
 86         }
 87         s.transitions.put(cNext, getState(newPositions));
 88         System.err.println("Adding edge " + s + " -" + cNext + "-> " + s.transitions.get(cNext));
 89     }
 90     public int search(E[] searchFor, E[] searchIn)
 91     {
 92         State<E> curState = initialState;
 93         int curPos;
 94         for (curPos = 0; curPos < searchIn.length && !curState.finale; curPos++)
 95         {
 96             curState = curState.transitions.get(searchIn[curPos]);
 97             if (curState == null)
 98                 curState = initialState;
 99         }
100         if (curState.finale)
101             return curPos - searchFor.length;
102         else
103             return -1;
104     }
105     private static Character[] str2charArray(String str) {
106         Character[] result = new Character[str.length()];
107         for (int i = 0; i < str.length(); i++)
108             result[i] = str.charAt(i);
109         return result;
110     }
111 
112     public static void main(String[] args)
113     {
114         Character[] a = str2charArray(args[0]), b = str2charArray(args[1]);
115         DFAStringSearch<Character> foo = new DFAStringSearch<Character>(a);
116         int result = foo.search(a, b);
117         if (result == -1)
118             System.out.println("No match found.");
119         else
120         {
121             System.out.println("Matched at position " + result + ":");
122             System.out.println(args[1].substring(0, result) + "|" + args[1].substring(result));
123         }
124     }
125 
126 }


hijacker
hijacker
hijacker
hijacker