Scout Algorithm For Fast Substring Matching
Exact substring matching is a common task in many software applications. Despite the existence of several algorithms for finding whether or not a pattern string is present in a target string, the most common implementation is a na\"ive, brute force approach. Alternative approaches either do not provide enough of a benefit for the added complexity, or are impractical for modern character sets, e.g., Unicode. We present a new algorithm, Scout, that is straightforward, quick and appropriate for all applications. We also compare the performance characteristics of the Scout algorithm with several others.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
MTD(f), A Minimax Algorithm Faster Than NegaScout
MTD(f) is a new minimax search algorithm, simpler and more efficient than previous algorithms. In tests with a number of tournament game playing programs for chess, checkers and Othello it performed better, on average, t…
Permutation Matching Under Parikh Budgets: Linear-Time Detection, Packing, and Disjoint Selection
We study permutation (jumbled/Abelian) pattern matching over a general alphabet $Σ$. Given a pattern P of length m and a text T of length n, the classical task is to decide whether T contains a length-m substring whose P…
Adaptive Substring Extraction and Modified Local NBNN Scoring for Binary Feature-based Local Mobile Visual Search without False Positives
In this paper, we propose a stand-alone mobile visual search system based on binary features and the bag-of-visual words framework. The contribution of this study is three-fold: (1) We propose an adaptive substring extra…
Image RetrievalRetrievalFast Search on Binary Codes by Weighted Hamming Distance
Weighted Hamming distance, as a similarity measure between binary codes and binary queries, provides superior accuracy in search tasks than Hamming distance. However, how to efficiently and accurately find $K$ binary cod…
Interpolated Spectral NGram Language Models
Spectral models for learning weighted non-deterministic automata have nice theoretical and algorithmic properties. Despite this, it has been challenging to obtain competitive results in language modeling tasks, for two m…
Language ModelingLanguage Modelling