Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Substring
Summary
In formal language theory and computer science, a substring is a contiguous sequence of characters within a 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 is a substring of that occurs at the beginning of ; likewise, a suffix of a string is a substring that occurs at the end of .
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).
A string is a substring (or factor) of a string if there exists two strings and such that . In particular, the empty string is a substring of every string.
Example: The string ana is equal to substrings (and subsequences) of banana at two different offsets:
banana
|||||
ana||
|||
ana
The first occurrence is obtained with b and na, while the second occurrence is obtained with ban and being the empty string.
A substring of a string is a prefix of a suffix of the string, and equivalently a suffix of a prefix; for example, nan is a prefix of nana, which is in turn a suffix of banana. If is a substring of , 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).
String operations#Prefixes
A string is a prefix of a string if there exists a string such that . A proper prefix of a string is not equal to the string itself; some sources in addition restrict a proper prefix to be non-empty. A prefix can be seen as a special case of a substring.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.