Substring: Difference between revisions

Revision as of 13:37, 7 October 2019

Revision as of 08:03, 8 October 2019

Line 9:

== 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>ps</math> such that <math>t = pus</math>. In particular, the empty string is a substring of every string. A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. If <math>s</math> is a substring of <math>t</math>, it is also a [[subsequence]], which is a more general concept. Given a pattern, you can find its occurrences in a string 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]].

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

Line 18:

|||

ana

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

In the mathematical literature, substrings are also called '''subwords''' (in America) or '''factors''' (in Europe).