NIST

strsrch

(algorithm)

Definition: Find occurrences of a substring in a target string by trying the substring at each possible location in the string. Execution time is Θ(mn), where m is length of the target string and n is the length of the substring.

Generalization (I am a kind of ...)
string matching.

Aggregate child (... is a part of or used in me.)
brute force string search.

Note: This is a C implementation of an APL routine. There are far faster algorithms at string matching.

As written, the routine uses a fixed size array (15 in the article) to return matching locations. Hence it only returns the first 15 locations.

Author: PEB

More information

Sanford J. Hersh, String Searching in C, Computer Language, 5(12):63-65, December 1988.


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 20 July 2018.
HTML page formatted Fri Jul 20 16:31:26 2018.

Cite this as:
Paul E. Black, "strsrch", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 20 July 2018. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/strsrch.html