The Prague Stringology Club Workshop '96
Space Complexity of Linear Time Approximate String Matching
| Abstract: |
| Approximate string matching is a sequential problem and therefore it is possible to solve it using finite automata. Nondeterministic finite automata are constructed for string matching with k mismatches and k differences. The corresponding deterministic finite automata are base for approximate string matching in linear time. Then the space complexity of both types of deterministic automata is calculated. Moreover, reduced versions of nondeterministic automata are taken into account and the space complexity of their deterministic equivalents is calculated. |
| Download paper: |  |
 |
| PostScript |