What string operations are basic What string operations are basic in the sense that the other string operations can be represented in terms of them? Here is a list of string operations off the top of my head (not necessarily a complete list, and your addition is welcome):


reversal of a string
concatenation of two strings
repetition of a string a finite number of times
search/match a string inside another string
match and replace a string with another string inside a string
split a string, at some specified positions, or according to matching result of another string
taking a substring out of a string, according to specified positions (including taking prefix, or suffix), or according to matching result of another string
...
There are many "complete bases" for operations on strings. One is based on the representation
$$ \Sigma^* = \epsilon + \Sigma \Sigma^*. $$
In words, a string is either empty or is composed of a character and a string. In order to use this representation, we need the following functions:


nil – the empty string
cons(x,s) – the string consisting of the character x followed by the string s
null(s) – true if s is empty
car(s) – returns the first character of a non-empty string
cdr(s) – returns the string resulting from removing the first character of a non-empty string


The terminology is from Lisp; cdr is read could-er or cudder.

Another basis considers strings as arrays. There is a standard basis for reading strings:


len(s) – the length of s
s[i] – the character at position i


For writing strings there are several options. In the immutable case, one choice is:


"" – the empty string
str(x) – the string consisting of the character x
cat(s1,s2) – the string resulting from concatenating s1 and s2


If strings are allowed to be mutable, we can add an operation s[i] = x, changing the character at position i to be x.

One can think of many other bases. Some will be more efficient than others. It all depends on what exactly you are trying to capture, what your goal is.