Substring: Difference between revisions

Revision as of 04:56, 31 May 2020

Latest revision as of 07:25, 30 May 2025

(36 intermediate revisions by 22 users not shown)

Line 1:

{{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''". ThisIn is not to be confused with [[subsequence]], which is a [[generalization]] of substring. For examplecontrast, "''Itwastimes''" is a subsequence of "''It was the best of times''", but not a substring.

[[Prefix]]es'''Prefixes''' and [[suffix]]es'''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 list of all substrings of the string "''apple''" would be :
"''applea''", "''applap''", "''ppleapp''", "''appappl''", "''pplapple''",
"''plep''", "''appp''", "''ppppl''", "''plpple''",
"''lepl''", "''aple''",
"''pl''", "''lle''",
"''e''", "".

(note the [[empty string]] at the end).

== Substring ==

Line 22 ⟶ 30:

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 ==

Line 39 ⟶ 47:

== 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>:

Line 51 ⟶ 59:

== Border ==

A border is suffix and prefix of the same string, e.g. "bab" is a border of "babab" (and also of "babooneatingakebabbaboon 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. Generally, one is interested in finding superstrings whose length is as small as possible;{{Clarify|reason=why are we interested in them?|date=June 2010}} a concatenation ofConcatenating all stringsmembers of <math>P</math>, in anyarbitrary order, always givesobtains 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 ==

Line 67 ⟶ 77:

| last = Gusfield

| first = Dan

| origyearorig-year = 1997

| year = 1999

| title = Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology

| publisher = Cambridge University Press

| ___location = USAUS

| isbn = 0-521-58519-8

}}</ref>

Line 93 ⟶ 103:

}}</ref>

}}

==External links==

*{{Commonscatinline}}

[[Category:String (computer science)]]