A fast string searching algorithm

摘要: An algorithm is presented that searches for the location, “il” of first occurrence a character string, “pat,” in another “string.” During search operation, characters pat are matched starting with last pat. The information gained by match at end pattern often allows to proceed large jumps through text being searched. Thus has unusual property that, most cases, not all i string inspected. number actually inspected (on average) decreases as function length For random English 5, will typically inspect i/4 before finding i. Furthermore, been implemented so fewer than + patlen machine instructions executed. These conclusions supported empirical evidence and theoretical analysis average behavior algorithm. worst case linear patlen, assuming availability array space tables plus size alphabet.