Chapter 3
String Processing
[Link] is a String?
String is a sequence of characters terminated by a
NULL Character
Or
String is an array of characters, terminated by a
NULL Character.
Example:
Burger
Char A[7];
A[0] A[1] A[2] A[3] A[4] A[5] A[6]
B u r g e r \0
Length of the String = 6
[Link] the different storage representation of the
strings
Storage representation of Strings:
Variable Length
Fixed Length
Length Controlled Delimited String
String
Fixed Length String Format:
Char A[10] = “Program” Blank Char
A[0] A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
P R O G R A M
Char A[15] = “Hello world”
Disadvantages:
1. If the length of the string is too small it is
applicable, but if the string is too large, the
fixed length string format is not possible.
2. Too much of memory is wasted.
3. The length of the string is fixed. It cannot be
changed.
4. The non-data characters such as space are
added at the end of the data
Variable Length string format:
The array storage structure for a string can be
expanded or shrink according to the number of
Characters.
Example:
Char a[] = “program in c ”
Length Controlled String:
A length controlled string is a string whose length is
stored as a part of the string itself.
Example:
Program
7 P R O G R A M
String String
Lengt
h
Delimited String:
The String which ends with a delimiter ( NULL or
Denoted by \0) Character.
Example:
Program
-------- -----8 Bytes---------------------------
P R O G R A M \0
String Delimite
r
Explain the string as ADT
String Operations:
1. String length
#include<stdio.h>
#include<string.h>
int main()
{
char str[100];
int len=0;
printf("\nEnter the string:");
gets(str);
// Calculating string length
while (str[len] != '\0')
{
len++;
}
printf("\Length of string is :%d", len);
return 0;
}
Example:
Str[0] Str[1] Str[2] Str[3]
U M A \0
0 1 2 3
Str[0]=> U !=’\0’ True Len = 1
Str[1]=> M !=’\0’ True Len = 2
Str[2}=> A !=’\0’ True Len = 3
Str[3]=> \0 !=’\0’ False
It will come out from the while
loop
Output:
Length of the string is 3
String Concatenation(strcat – built in function)
Program without using builtin function
#include<stdio.h>
void main
{
char str1[25],str2[25];
int i=0,j=0;
printf("\nEnter First
String:");
gets(str1);
printf("\nEnter Second
String:");
gets(str2);
while(str1[i]!='\0')
i++;
while(str2[j]!='\0')
{
str1[i]=str2[j];
j++;
i++;
}
str1[i]='\0';
printf("\nConcatenated String
is %s",str1);
}
First String
0 1 2 3 4
U S H A \0
Str1[0 Str1[1 Str1[2 Str1[3 Str1[4
] ] ] ] ]
I=0,j=0
while(str1[i]!='\0')
i++;(i=i+1)
I = 0 Str1[0]=> u!='\0' T i= 1
I=1 str1[1] => s!='\0' T I =2
I =2 str1[2]=> H!='\0' T I =3
I =3 str1[3] => A!='\0' T I =4
I =4 Str1[4]=>\0!='\0' F
Second string
0 1 2 3
R A m \0
Str2[0 Str2[1 Str2[2 Str2[3
] ] ] ]
while(str2[j]!='\0')
{
str1[i]=str2[j];
j++;
i++;
}
J=0 str2[0]= R !='\0' T j = 1 I
=5
J=1 str2[1] =>a!='\0' T j =2 i=6
J=3, I =7
STR1 string
I =0 1 2 3 4 5 6 7
u s h a R a m \0
J
After Concatenation
String Comparison:
To Check whether both the strings are equal
or not.
Program without using built in fuctions
#include<stdio.h>
#include<conio.h>
Void main()
{
Char str1[40],str2[40];
Int i=0,j=0;
printf(“Enter the first string”);
gets(str1);
printf(“Enter the Second string”);
gets(str2);
while(str1[i]==str2[j] && str1[i]!=’\0’)
{
I++;
J++;
}
if(str1[i]==str2[j])
Printf(“Strings are equal:”);
Else
Printf(“strings are not equal”);
}
First String
Str1[0 Str1[1 Str1[2 Str1[3 Str1[4 Str1[5
] ] ] ] ] ]
A R R O w \0
I =0 1 2 3 4 5
Second string
Str2[0 Str2[1 Str2[2 Str2[3 Str2[4 Str2[5
] ] ] ] ] ]
a R R O w \0
I =0 1 2 3 4 5
Str2[0 Str2[1 Str2[2 Str2[3
] ] ] ]
A A T \0
J =0 1 2 3
X Y X || Y(Add)
0 (F) 0 (F) 0
0(F) 1 (T) 1
1 0 1
1 1 1
Substring
To get the substring from the string, it requires the
following
1. String
2. Start Position
3. Length
“Madam is teaching”
Starting position is 2
10 dam i
Program to find the substring from the given string:
#include <Stdio.h>
#include <conio.h>
int main()
{
char str[100], substr[100];
int i=0, j=0, n, m;
clrscr ();
printf("\n Enter the main string: ");
gets (str); //read a string
printf("\n Enter the position from
which to start the substring: ");
scanf ("%d", &m) ;
printf("\n Enter the length of the
substring: ") ;
scanf ("%d", &n);
i=m;
while(str[i] !='\0' &&n>=0)
{
substr[j] = str[i];
i++;
j ++;
n--;
}
substr[j] = '\0';
printf ("\n The substring is : ");
puts (str);
getch();
return 0;
}
Output:
Enter the string
Raju is dancing
Str Str Str Str Str Str Str Str Str Str Str[ Str[ Str[ Str[ Str[ Str[
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] 10] 11] 12] 13] 14] 15]
R A J U I S D A N C I N G \0
= 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
i0 I I I I
= = = =
6 7 8 9
Enter the position from which to start the
substring.
m = 6
Enter the length of the substring:
n = 7
i=m;
while(str[i] !='\0' &&n>=0)
{
substr[j] = str[i];
i++;
j ++;
n--;
}
substr[j] = '\0';
printf ("\n The substring is : ");
puts(substr);
}
substr
subst Subst Subst Subst Substr[4 Substr[5 Substr[6 Substr[7 Substr[8
r [0] r r r ] ] ] ] ]
[1] [2] [3]
s D A N C I N \0
J =0 1 2 3 4 5 6 7 8
i =6 n =7
str[6] !=\0 =>T and 7>=0 => t
j=0 substr[0]=str[6]
i++, j++, n--;=>i=7, j=1, n= 6
i++, j++, n--;=>i=8, j=2, n= 5
i++, j++, n--; = > i=9,j=3,n=4
i++, j++, n--; => i=10, j=4,n=3
i++, j++, n--; => i=11, j=5,n=2
i++, j++, n--; => i=12, j=6, n=1
i++, j++, n--; = > i=13 , j=7, n=0
i++, j++, n--; => i=14, j=8, n=-1
Indexing:
It is also pattern matching. Find out the position of
a pattern(Substring) in a given string.
Example:
“Data structures”,”struct”
To find the index of pattern in a string
#include<sdtio.h>
#include<conio.h>
Void main()
{
Char str[100],substr[50];
Int i =0,j,k=0;
Printf(“Enter the string:”);
gets(str);
Printf(“Enter the substring:”);
gets(substr);
while(str[i]!=’\0’)
{
If(str[i]==substr[0])
{
j =1;
while(substr[j]!=’\0’ && str[j+i]!=’\0’
&&substr[j]==str[j+i])
{
j++;
K =1;
}
If(substr[j]==’\0’)
Printf(“Pattern String is found at %d position”,i+1);
}
i++;
if(k==0)
{
If(str[j+i]==’\0’)
Printf(“pattern not found”);
}
Getch();
}
Enter the string
ramu
Str[0] Str[1] Str[2] Str[3] Str[4]
R A M U \0
0 1 2 3 4
Substring:
mu
subStr[0] subStr[1] subStr[2]
m u \0
0 1 2
While(str[0]!=’\0) => R ! =’\0’ True
R ==Substr[0]=> R ==m
Word Procesiing
It is used to create, edit and print the documents.
Operation:
1. Insertion: In a given string, we want to insert
a substring in some position.
Example:
Insert(“hello world”,5,”world”);
=helloworldworld
2. Deletion:
In a given string , we want to delete the string
from the position and also the [Link]
charcters(length)
Example:
DELETE(STR, POS, LEN)
Delete(“Data Structures”,10,5);
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
D A T A S T R U C T U R E S
Output
Data struc
3. Replacement:
In a given string , we want to replace the first
occurrence of pattern p1 by a pattern p2.
Example:
Replace(str, p1,p2)
Replace(“Second Semester BCA”,”
ester”,”Super”)
Output:
Second SemSuper BCA
Replace(“Favaz Khan”,”Khan”,”Don”)
Favaz Don
Write a algorithm to insert a string in a given
string.
Algorithm:
INSERT(STR, POS,NEWSTR)
//STR is a given string,we want to insert a string
NEWSTR in apposition POS
Step1:
First: = SUBSTRING(STR, 1, POS-1)
Step 2:
Concatenate First and NEWSTR
CONSTR:= First +NEWSTR
Step 3:
Second:=SUBSTRING(STR, POS,LENGTH(STR))
Step 4:
Final String :=CONSTR + SECOND
Explanation:
Let us consider the string “ANU”
1 2 3
A N u
We would like to insert “Kapoor” at 2nd position
STR = “ANU”
NEWSTR =”Kapoor”
POS =2
Step1:
First := substring(“ANU”,1,1)
First: =”A”
1 2 3
A N u
Step2:
Concatenate first and NEWSTR
CONSTR:=First + NEWSTR
CONSTR =AKapoor
Step 3:
Second:= SUBSTRING(“ANU”, 2,3)
Second:= NU
Step 4:
CONSTR =AKapoor
Second:= NU
Final STR = AKapoorNU
Write an Algorithm to delete a string from a given
string.
Algorithm:
DELETE(STR,POS,LEN)
//STR is a Given string, We want to delete from
position POS of Length LEN. The Delete operation
can be implemented using SUBSTRING Operation.
Step 1:
First: = SUBSTRING(STR, 1, POS-1)
Step 2:
Second:=SUBSTRING(STR, POS +LEN,LENGTH(STR))
Step 3:
Concatenate the strings
Final String :=First + Second
Enter the string
1 2 3 4 5 6 7 8 9 10 11
H E L L O W O r L d
STR =”HELLO WORLD”
POS =3
LEN =6 “LLO WO” to be deleted
Step 1:
Extract the substring from the first letter till pos -1
(POS – 1 => 3 -1 =(2))
1 2 3 4 5 6 7 8 9 10 11
H E L L O W O r L d
First: = SUBSTRING(“HELLO WORLD”, 1, 2)
FIRST : =”HE”
Step 2:
Extract the substring from POS + LEN till the length
of the string
Second:=SUBSTRING(STR, POS +LEN,LENGTH(STR))
Length of STR =”HELLO WORLD”
=11
POS +LEN = 3 + 6 =9
Second:= SUBSTRING(“HELLO WORLD”,9,11)
1 2 3 4 5 6 7 8 9 10 11
H E L L O W O r L d
Second: =”rld”
Step 3:
Concatenate the strings
Final String :=First + Second
=”HE” + “RLD”
Final String =”HERLD”
1 2 3 4 5
H E R L D
Write the algorithm to replace a string in a given
string
Algorithm :
REPLACE( STR, P1, P2)
//Given a string is [Link] want to replace the first
occurrence of Pattern P1 by a Pattern P2
Step 1:
We need the index of P1
POS:=INDEX(STR, P1)
STEP 2:
Delete the pattern P1 from the string STR
STR : = DELETE(STR, POS,LENGTH(P1))
STEP3:
Insert P2 in the string STR at Position POS
INSERT(STR, POS,P2)
Example:
Enter the String
STR = “SWEET HOME”
1 2 3 4 5 6 7 8 9 10
S W E E T H O M E
P1 =”SWEET”
P2 =”GREAT”
Step1:
POS:=INDEX(STR, P1)
POS : =INDEX(“SWEET HOME”,”SWEET”)
POS:= 1
1 2 3 4 5 6 7 8 9 10
S W E E T H O M E
(Position of the first character ie ‘S’)
Step 2:
STR : = DELETE(STR, POS,LENGTH(P1))
LENGTH(P1) => LENGTH(“SWEET”) = 5
STR : = DELETE(“SWEET HOME”,1, 5)
STR : = “ HOME”
1 2 3 4 5 6 7 8 9 10
H O M E
Step 3:
INSERT(STR, POS,P2)
INSERT (“SWEET HOME”, 1,”GREAT”)
STR =”GREAT HOME”
1 2 3 4 5 6 7 8 9 10
G R E A T H O M E
Pattern Matching Algorithm
Naïve Pattern Searching Algorithm
Algorithm:
//give a string str[0…..n-1] and pattern pat[0….m-
1]
Step1:
j:=1
Step 2: while (j<=n-m+1) do begin
Step 3: i:=1
Step 4: While(i<=m) and (pat[i]=str[j]) do begin
Step 5: i:= i+1
Step 6: j:=j+1
end while
Step 7:if(i<=m) then j:= j-i+2
Step 8: else write(“Found at”, j-i+1)
Step 9: end
Best Case
NO. of Comparisions = O(n)
Worst Case:
O(mn)
Kunth –Morries –Pratt Algorithm(KMP Algorithm)
“str[] =search” Pat[]=“ar”
Lps[]=
Str[] = “BBBBBB” n
Pat[] =”BBC
Lps ={ 0,1,2,3,4,5,}