Loading...
Please wait, while we are loading the content...
Similar Documents
An exact string matching algorithm based upon the substring encoding method.
| Content Provider | CiteSeerX |
|---|---|
| Author | Chen, H. M. Lee, R. C. T. |
| Description | This content is published in/by THE 25TH WORKSHOP ON COMBINATORIAL MATHEMATICS AND COMPUTATION THEORY |
| Abstract | The traditional exact string matching problem is to find all locations of a pattern string with length m in a text with length n. Here we propose a new encoding method to shorten the both lengths of pattern and text by substituting the substring between a special character for its length in Ο ( m + n). Then we use an exact matching algorithm to solve the exact string matching problem on the encoding pattern and text. As can be seen, by using the encoding method, the pattern and text can be shortened about 2 Σ times the lengths of the original ones. In practice, it performs better than 2 Σ. For instance, for an English sentence pattern whose length is 20 and a text whose length is 5000, in average, the pattern is shortened to 16.5 % of its original length and the text is shortened to 15.5 % of its original length. Thus, the exact matching can be done in a much shorter time. Secion |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Substring Encoding Method Exact String Matching Algorithm Original Length Original One English Sentence Pattern Exact Matching Special Character Exact String Matching Problem Encoding Pattern |
| Content Type | Text |
