0-Introduction
Application of String Processing
- Information Processing
- Genomics
- Communication Books
- Programming Systems
Rules of the Game
For clarity there are several assumptions and definitions that we will make use of ahead.
- Characters : A
String is a sequence of characters. Characters are of type char.
- Immutability : String objects are immutable. Their values doesn’t change while assigning statements and as arguments and return values.
- Indexing : Operation to extract a specified character from a string.
- Length :
- Substring : extract a specified substring operation. We expect a constant time implementation of this.
- Concatenation : Creating a new string by appending one string to another.
- Character Arrays : We can alternately use an array of character as direct abstraction for string.
Main point to focus here is understanding the efficiency of each operation.
Not all languages provide same implementation of String for e.g. in C it may take linear time to determine the length of String.