imported>Graue: this has a cite in the body immediately below

2025-05-30T07:25:54Z

this has a cite in the body immediately below

New page

{{Short description|Contiguous part of a sequence of symbols}}
{{About|the definition of a substring|the computer function which performs this operation|String functions (programming)}}
{{Distinguish|text=[[subsequence]], a generalization of substring}}
[[File:Substring.png|thumb|"''string''" is a substring of "''substring''"]]

In [[Formal language|formal language theory]] and [[computer science]], a '''substring''' is a contiguous sequence of [[Character (computing)|character]]s within a [[String (computer science)|string]]. For instance, "''the best of''" is a substring of "''It was the best of times''". In contrast, "''Itwastimes''" is a subsequence of "''It was the best of times''", but not a substring.

'''Prefixes''' and '''suffixes''' are special cases of substrings. A prefix of a string <math>S</math> is a substring of <math>S</math> that occurs at the beginning of <math>S</math>; likewise, a suffix of a string <math>S</math> is a substring that occurs at the end of <math>S</math>.

The substrings of the string "''apple''" would be:
"''a''", "''ap''", "''app''", "''appl''", "''apple''",
"''p''", "''pp''", "''ppl''", "''pple''",
"''pl''", "''ple''",
"''l''", "''le''"
"''e''", ""
(note the [[empty string]] at the end).

== Substring ==

A string <math>u</math> is a substring (or factor)<ref name=Lot97/> of a string <math>t</math> if there exists two strings <math>p</math> and <math>s</math> such that <math>t = pus</math>. In particular, the empty string is a substring of every string.

Example: The string <math>u=</math><code>ana</code> is equal to substrings (and subsequences) of <math>t=</math><code>banana</code> at two different offsets:

banana
|||||
ana||
|||
ana

The first occurrence is obtained with <math>p=</math><code>b</code> and <math>s=</math><code>na</code>, while the second occurrence is obtained with <math>p=</math><code>ban</code> and <math>s</math> being the empty string.

A substring of a string is a [[#Prefix|prefix]] of a [[#Suffix|suffix]] of the string, and equivalently a suffix of a prefix; for example, <code>nan</code> is a prefix of <code>nana</code>, which is in turn a suffix of <code>banana</code>. If <math>u</math> is a substring of <math>t</math>, it is also a [[subsequence]], which is a more general concept. The occurrences of a given pattern in a given string can be found with a [[string searching algorithm]]. Finding the longest string which is equal to a substring of two or more strings is known as the [[longest common substring problem]].
In the mathematical literature, substrings are also called '''subwords''' (in America) or '''factors''' (in Europe). {{citation needed|date=November 2020}}

== Prefix ==
{{see also|String operations#Prefixes}}
A string <math>p</math> is a prefix<ref name=Lot97/> of a string <math>t</math> if there exists a string <math>s</math> such that <math>t = ps</math>. A ''proper prefix'' of a string is not equal to the string itself;<ref name=Kel95/> some sources<ref name=Gus97/> in addition restrict a proper prefix to be non-empty. A prefix can be seen as a special case of a substring.

Example: The string <code>ban</code> is equal to a prefix (and substring and subsequence) of the string <code>banana</code>:

banana
|||
ban

The square subset symbol is sometimes used to indicate a prefix, so that <math>p \sqsubseteq t</math> denotes that <math>p</math> is a prefix of <math>t</math>. This defines a [[binary relation]] on strings, called the [[prefix relation]], which is a particular kind of [[prefix order]].

== Suffix ==

A string <math>s</math> is a suffix<ref name=Lot97/> of a string <math>t</math> if there exists a string <math>p</math> such that <math>t = ps</math>. A ''proper suffix'' of a string is not equal to the string itself. A more restricted interpretation is that it is also not empty.{{ref|Gus97}} A suffix can be seen as a special case of a substring.

Example: The string <code>nana</code> is equal to a suffix (and substring and subsequence) of the string <code>banana</code>:

banana
||||
nana

A [[suffix tree]] for a string is a [[trie]] [[data structure]] that represents all of its suffixes. Suffix trees have large numbers of applications in [[String (computer science)#String processing algorithms|string algorithms]]. The [[suffix array]] is a simplified version of this data structure that lists the start positions of the suffixes in alphabetically sorted order; it has many of the same applications.

== Border ==

A border is suffix and prefix of the same string, e.g. "bab" is a border of "babab" (and also of "baboon eating a kebab").{{citation needed|date=January 2022}}

== Superstring ==

A '''superstring''' of a finite set <math>P</math> of strings is a single string that contains every string in <math>P</math> as a substring. For example, <math>\text{bcclabccefab}</math> is a superstring of <math>P = \{\text{abcc}, \text{efab}, \text{bccla}\}</math>, and <math>\text{efabccla}</math> is a shorter one. Concatenating all members of <math>P</math>, in arbitrary order, always obtains a trivial superstring of <math>P</math>. Finding superstrings whose length is as small as possible is a more interesting problem.

A string that contains every possible permutation of a specified character set is called a [[superpermutation]].

== See also ==
* [[Brace notation]]
* [[Substring index]]
* [[Suffix automaton]]

==References==
{{Reflist|refs=
<ref name=Gus97>{{cite book
| last = Gusfield
| first = Dan
| orig-year = 1997
| year = 1999
| title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
| publisher = Cambridge University Press
| location = US
| isbn = 0-521-58519-8
}}</ref>
<ref name=Kel95>{{cite book
| last = Kelley
| first = Dean
| year = 1995
| title = Automata and Formal Languages: An Introduction
| publisher = Prentice-Hall International
| location = London
| isbn = 0-13-497777-7
}}</ref>
<ref name=Lot97>{{cite book
| last = Lothaire
| first = M.
| year = 1997
| title = Combinatorics on words
| publisher = Cambridge University Press
| location = Cambridge
| isbn = 0-521-59924-5
}}</ref>
}}

[[Category:String (computer science)]]
[[Category:Formal languages]]

Substring - Revision history

imported>Graue: this has a cite in the body immediately below