Editing String (computer science) (section)

==== Length-prefixed ====
The length of a string can also be stored explicitly, for example by prefixing the string with the length as a byte value. This convention is used in many [[Pascal (programming language)|Pascal]] dialects; as a consequence, some people call such a string a '''Pascal string''' or '''P-string'''. Storing the string length as byte limits the maximum string length to 255. To avoid such limitations, improved implementations of P-strings use 16-, 32-, or 64-bit [[Word (data type)|words]] to store the string length. When the ''length'' field covers the [[address space]], strings are limited only by the [[Dynamic memory allocation|available memory]].

If the length is bounded, then it can be encoded in constant space, typically a machine word, thus leading to an [[implicit data structure]], taking ''n'' + ''k'' space, where ''k'' is the number of characters in a word (8 for 8-bit ASCII on a 64-bit machine, 1 for 32-bit UTF-32/UCS-4 on a 32-bit machine, etc.).
If the length is not bounded, encoding a length ''n'' takes log(''n'') space (see [[fixed-length code]]), so length-prefixed strings are a [[succinct data structure]], encoding a string of length ''n'' in log(''n'') + ''n'' space.

In the latter case, the length-prefix field itself does not have fixed length, therefore the actual string data needs to be moved when the string grows such that the length field needs to be increased.<!---commented out: "bad" is not an issue in a technical encyclopedic article---This in itself is not that bad since the number of bytes is just logarithmic on the length of string,---><!---commented out: while NULL-terminated string allow for pointers to proper substrings, length-prefixed strings do not; a pointer to a length-prefixed string has to point to the length field, which remains at the same location after growing--- but the downside is that any direct pointers to the string data get invalidated (they should move by one).--->

Here is a Pascal string stored in a 10-byte buffer, along with its ASCII / UTF-8 representation:

{| class="wikitable" style="margin-left: auto; margin-right:auto"
 |-
 | <small>length</small>
 | <code>F</code>  || <code>R</code>  || <code>A</code>  || <code>N</code>  || <code>K</code>
 | style="background: #DDD" | <code style="background: #DDD">k</code>
 | style="background: #DDD" | <code style="background: #DDD">e</code>
 | style="background: #DDD" | <code style="background: #DDD">f</code>
 | style="background: #DDD" | <code style="background: #DDD">w</code>
 |-
 | 05<sub>16</sub>
 | 46<sub>16</sub> || 52<sub>16</sub> || 41<sub>16</sub> || 4E<sub>16</sub> || 4B<sub>16</sub>
 | style="background: #DDD" | 6B<sub>16</sub>
 | style="background: #DDD" | 65<sub>16</sub>
 | style="background: #DDD" | 66<sub>16</sub>
 | style="background: #DDD" | 77<sub>16</sub>
 |}