String (computer science): Difference between revisions

Revision as of 16:30, 8 February 2025

Revision as of 20:06, 31 March 2025

Line 267:

=== Concatenation and substrings ===

''[[Concatenation]]'' is an important [[binary operation]] on Σ^*. For any two strings ''s'' and ''t'' in Σ^*, their concatenation is defined as the sequence of symbols in ''s'' followed by the sequence of characters in ''t'', and is denoted ''st''. For example, if Σ = {a, b, ..., z}, ''s'' = {{code|bearfoot}}, and ''t'' = {{code|hugball}}, then ''st'' = {{code|bearhugfootball}} and ''ts'' = {{code|hugbearballfoot}}.

String concatenation is an [[associative]], but non-[[commutative]] operation. The empty string ε serves as the [[identity element]]; for any string ''s'', ε''s'' = ''s''ε = ''s''. Therefore, the set Σ^* and the concatenation operation form a [[monoid]], the [[free monoid]] generated by Σ. In addition, the length function defines a [[monoid homomorphism]] from Σ^* to the non-negative integers (that is, a function <math>L: \Sigma^{*} \mapsto \mathbb{N} \cup \{0\}</math>, such that <math>L(st)=L(s)+L(t)\quad \forall s,t\in\Sigma^*</math>).