Han, YS
Wood, D
2024-01-21T04:33:33Z
2024-01-21T04:33:33Z
2021-09-01
2005-09
0302-9743
https://pubs.kist.re.kr/handle/201004/136197
In the pattern matching problem, there can be a quadratic number of matching substrings in the size of a given text. The linearizing restriction finds, at most, a linear number of matching substrings. We first explore two well-known linearizing restriction rules, the longest-match rule and the shortest-match substring search rule, and show that both rules give the same result when a pattern is an infix-free set even though they have different semantics. Then, we introduce a new linearizing restriction, the leftmost non-overlapping match rule that is suitable for find-and-replace operations in text searching, and propose an efficient algorithm when the pattern is a regular language according to the new match rule.
English
SPRINGER-VERLAG BERLIN
ALGORITHM
SEARCH
A new linearizing restriction in the pattern matching problem
Article
1
FUNDAMENTALS OF COMPUTATIONAL THEORY, PROCEEDINGS, v.3623, pp.552 - 562
FUNDAMENTALS OF COMPUTATIONAL THEORY, PROCEEDINGS
3623
552
562
scie
scopus
000233547100048
Computer Science, Theory & Methods
Computer Science
Article; Proceedings Paper
ALGORITHM
SEARCH
automata and formal languages
design and analysis of algorithms
string pattern matching