Content deleted Content added
Tags: Mobile edit Mobile web edit |
Undid revision 907378369 by 2409:4072:80F:8D76:0:0:C62:E0A4 (talk) |
||
Line 9:
== Substring ==
A substring (or factor) of a string <math>T = t_1 \dots t_n</math> is a string <math>\hat T = t_{1+i} \dots t_{m+i}</math>, where <math>0 \leq i</math> and <math>m + i \leq n</math>. A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix. If <math>\hat T</math> is a substring of <math>T</math>, it is also a [[subsequence]], which is a more general concept. Given a pattern <math>P</math>, you can find its occurrences in a string <math>T</math> 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 <code>ana</code> is equal to substrings (and subsequences) of <code>banana</code> at two different offsets:
| |||