Loading...
Please wait, while we are loading the content...
Similar Documents
String Matching using Inverted Lists
| Content Provider | Semantic Scholar |
|---|---|
| Author | Khancome, Chouvalit Boonjing, Veera |
| Copyright Year | 2007 |
| Abstract | This paper proposes a new solution to string matching problem. This solution constructs an inverted list representing a string pattern to be searched for. It then uses a new algorithm to process an input string in a single pass. The preprocessing phase takes 1) time complexity O(m) 2) space complexity O(1) where m is the length of pattern. The searching phase time complexity takes 1) O(m+α ) in average case 2) O(n/m) in the best case and 3) O(n) in the worst case, where α is the number of comparing leading to mismatch and n is the length of input text. Keywords—String matching, inverted list, inverted index, pattern, algorithm. |
| Starting Page | 39 |
| Ending Page | 43 |
| Page Count | 5 |
| File Format | PDF HTM / HTML |
| Volume Number | 1 |
| Alternate Webpage(s) | http://waset.org/publications/7400/string-matching-using-inverted-lists- |
| Alternate Webpage(s) | http://www.waset.org/journals/waset/v25/v25-20.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
