String operations

Different types of string operations are,

Substrings

A substring is the basic unit of access in a string. Unlike other array elements, substrings have their own meaning. To access a substring we need the following information,

• Name of the string.
• Position of the first character of the substring in the given string.
• length of the substring.

Algorithm SUBSTRING (SUBSTR,STR,INITIAL,LENGTH)

1. STRLEN=LENGTH(STR)
2. If STRLEN < (INITIAL+LEN) Then Exit
3. SET I=INITIAL AND J=0
4. REPEAT STEPS 5 TO 7 WHILE J<LEN
5.   SUBSTR[J]=STR[I]
6.   J=J+1
7.   I=I+1
8. EXIT

Here substring SUBSTR of length LEN is extracted from STR, starting from the location INITIAL.

if string A=’WELCOME’, then after SUBSTRING(SUB, A,3,2), the value of SUB will be ‘LC’.

Indexing

Indexing operation is used to find the position of the first appearance of a string pattern in a given string. It is also called pattern matching. INDEX operation returns a 0 if there is no such pattern in that string.

Algorithm INDEX (TEXT,PAT) – Naive Pattern Searching

1. LENSTR=LENGTH(TEXT)
2. LENPAT=LENGTH(PAT)
3. SET I=1 and MAX=LENSTR-LENPAT.
4. Repeat Step 5 to 7 while I<=MAX:
5.   Repeat for J=1 to LENPAT:
       If TEXT[I+J-1] ≠ PAT[J], then: Go to Step 7.
6.   SET INDEX=K, and EXIT.
7.   I=I+1.
8. SET INDEX=0.
9. Exit.

Here we search for pattern PAT in string TEXT. LENSTR is the length of the TEXT and LENPAT is the length of the PAT.

if A=’MORNING’ then INDEX(A,’NI’) will return, 4, the first appearance of pattern ‘NI’ in the given string ‘MORNING’.

Concatenation

if A and B are two strings, then the concatenation of two strings, A//B is the string that consisting of the characters of A followed by the characters of B.

Algorithm CONCATENATE (STR1, STR2,ST3)

1. LEN1=LENGTH(STR1).
2. LEN2=LENGTH(STR2).
3. SET I=0.
4. Repeat Steps 5 and 6 while I<LEN1-1:
5.     STR3[I]=STR1[I].
6.     SET I=I+1.
7. SET J=0.
8. Repeat Steps 9 to 11 while I<(LEN1+LEN2-2):
9.     STR3[I]=STR2[J].
10.    J=J+1.
11.    I=I+1.
12.Exit.

This algorithm concatenates ST2 to STR1 and form STR3.

if A=’GOOD’ and B=’MORNING’ then A//B will be ‘GOODMORNING’

Length

The number of characters in a string is called the length of that string.

Algorithm LENGTH(STRING)

1. SET LEN=0 AND I=0.
2. Repeat Steps 3 to 4 while STRING[I] is not NULL:
3. LEN=LEN+1.
4. SET I=I+1.
5. Exit.

if A=”DECEMBER” then LENGTH(A) will return 8.

Text Processing Operations

The processing of printed matter such as letters and articles are called word processing. Basic operations associated with word processing are,

• Replacement
• Insertion
• Deletion

Word processing operations can be done using string operations.

Insertion

INSERT(TEXT,POSITION,STRING) operation inserts STRING in TEXT so that STRING begins in POSITION.

For example INSERT(‘ABCDE’,2,’PQR’) = ‘APQRBCDE’

INSERT operation can be implemented using string operations as follows,

INSERT(T,K,S) = SUBSTRING(T,1,K-1) // S // SUBSTRING(T,K,LENGTH(T)-K+1)

That is the substring before the position K is concatenated with S and with the remaining part of the string T.

Deletion

For example DELETE(‘ABCDEF’,2,3) = ‘AEF’

DELETE operation can be implemented using string operations as follows,

DELETE(T,K,L) = SUBSTRING(T,1,K-1) // SUBSTRING(T,K+L,LENGTH(T)-K-L+1)

That is the substring before position k is concatenated with the substring starting at position K+L.

Replacing

REPLACE(TEXT,PATTERN1,PATTERN2) replaces the first occurrence of PATTERN1 by PATTERNP2 in TEXT.

For example REPLACE(‘PQRSTU’,’RS’,’X’) = PQXTU

REPLACE operation can be implemented using three-string operations as follows,

K=INDEX(TEXT,PATTERN1)
T=DELETE(TEXT,K,LENGTH(PATTERN1)
INSERT(TEXT,K,PATTERN2)

The first two steps delete the first occurance of PATTERN1 from TEXT and the third step insert PATTERN2 in that position.