Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Substring index
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a substring index is a <a href="/facts/Data_structure/yNsNvL1I">data structure</a> which gives <a href="/facts/Substring/dM5Rqg6X">substring</a> search in a text or text collection in <a href="/facts/Sublinear/u1NglYpF">sublinear</a> time. Once constructed from a document or set of documents, a substring index can be used to locate all occurrences of a pattern in time linear or near-linear in the pattern size, with no dependence or only logarithmic dependence on the document size. </p><p>The phrase full-text index is often used for substring indexes. But this is ambiguous, as it is also used for regular word indexes such as <a href="/facts/Inverted_file/Kyva3prq">inverted files</a> and <a href="/facts/Document_retrieval/H0n6LnCQ">document retrieval</a>. See <a href="/facts/Full_text_search/X0qrIEJj">full text search</a>. </p>