Substring

From Wikipedia, the free encyclopedia

(Redirected from Prefix order)

A subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string, where the order of the elements is preserved. In this context, the terms string and sequence have the same meaning.

1 Subsequence
2 Substring
3 Prefix
4 Suffix
5 References

Main article subsequence

A subsequence of a string $T = t_1 t_2 \dots t_n$ is a string $\hat T = t_{i_1} \dots t_{i_m}$ such that $i_1 < \dots < i_m$ , where $m \leq n$ . Subsequence is a generalisation of substring, suffix and prefix. Finding the longest string which is equal to a subsequence of two or more strings is known as the longest common subsequence problem.

Example: The string anna is equal to a subsequence of the string banana:

banana
 || ||
 an na

A substring of a string $T = t_1 \dots t_n$ is a string $\hat T = t_{1+i} \dots t_{m+i}$ , where $0 \leq i$ and $m + i \leq n$ . A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. If $\hat T$ is a substring of $T$ , it is also a subsequence, which is a more general concept. Given a pattern $P$ , you can find its occurrences in a string $T$ 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 ana is equal to substrings (and subsequences) of banana at two different offsets:

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

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

A prefix of a string $T = t_1 \dots t_n$ is a string $\widehat T = t_1 \dots t_{m}$ , where $m \leq n$ . A proper prefix of a string is not equal to the string itself and not empty^[1] ( $0 < m < n$ ). A prefix can be seen as a special case of a substring.

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

banana
|||
ban

The square subset symbol is sometimes used to indicate a prefix, so that $\widehat T \sqsubseteq T$ denotes that $\widehat T$ is a prefix of $T$ . This defines a binary relation on strings, called the prefix relation.

In formal language theory, the term prefix of a string is also commonly understood to be the set of all prefixes of a string, with respect to that language. See the article on string functions (mathematics) for more details.

A suffix of a string $T = t_1 \dots t_n$ is a string $\hat T = t_{n-m+1} \dots t_{n}$ , where $m \leq n$ . A proper suffix of a string is not equal to the string itself and not empty^[2] ( $0 < m < n$ ). A suffix can be seen as a special case of a substring.

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

banana
  ||||
  nana

^ Gusfield, Dan [1997] (1999). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.

Retrieved from "http://en.wikipedia.org/wiki/Substring"

Category: Algorithms on strings

Searching reference...

Reference

Sources

Substring

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Searching reference...

Reference

Sources

Substring

From Wikipedia, the free encyclopedia

Contents

Top Matching Results

Sponsored Links This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Sponsored Links
This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.