OPTIMAL CORRESPONDENCE OF STRING SUBSEQUENCES

The problem of substring matching when the strings are from a finite alphabet has been investigated thoroughly in the literature. The corresponding problem when the alphabet is infinite (for example strings of numbers) has received less attention. We present definitions of string distance, an effective way of computing them, and matching algorithms minimizing such distances. Our analysis also includes the matching of strings to regular expressions. We include two diverse applications: the stereo epipolar line matching and the bar code recognition. © 1990 IEEE