CSE-2101
Data Structures & Algorithms I
Rumana Yasmin
Lecturer
DCSE, FST, BUP
Chapter 2
Preliminaries
Mathematical Notations and Functions
• Floor Function
✓ Floor function of x denotes the greatest integer that does not exceed x
• Ceiling Function
✓ Ceiling Function of x denotes the least integer that is not less than x
• Remainder Function: Modular arithmetic
Chapter 3
String Processing
STRING
• Strings are defined as an array of characters.
• The difference between a character array and a string is the string
is terminated with a special character ‘\0’
• Substring
o A substring is a contiguous part of a string, i.e., a string inside another
string.
5
STRING OPERATIONS
• Substring
• Indexing
• Concatenation
• Length
6
SUBSTRING
• To access a substring from a given string we need:
1. The name of the string
2. The position of the first character of the substring in the given string
3. The length of the substring
SUBSTRING(string, initial, length)
• String, S = ‘PRINT TWO INTEGERS’
• SUBSTRING(S, 4, 7)
o ‘NT TWO ’
7
INDEXING
• Also known as Pattern matching
• Finds the position where the string pattern (P) first appears in the given
string text (T)
INDEX(text, pattern)
• T = ‘HIS FATHER IS THE PROFESSOR’
• INDEX(T, ‘THE’) = 7
• INDEX(T, ‘THEN’) = 0
• INDEX(T, ‘ THE ’) = 14
8
CONCATENATION
• Let S1 and S2 be two strings.
• The concatenation of S1 and S2 (denoted by S1//S2) is the string
consisting of the characters of S1 followed by the characters of
S2.
• S1 = ‘MUSHFIQUR’ strcat()
• S2 = ‘RAHIM’
• S1//S2 = ‘MUSHFIQURRAHIM’
• S1// //S2 = ‘MUSHFIQUR RAHIM’
9
LENGTH
• The number of characters in the string is called its length.
LENGTH(string)
• S = ‘COMPUTER SCIENCE’
• LENGTH(S) = 16
strlen()
• S1 = ‘ ’ Space
• LENGTH(S1) = ?
• S2 = ‘\0’ null character
• LENGTH(S2) = ?
10
WORD/TEXT PROCESSING
• Insertion
• Insert a substring to a specific position
• Deletion
• Delete a substring from a specific position
• Replacement
• Replace the first occurrence of a pattern P1 by another pattern P2
11
WORD/TEXT PROCESSING
• INSERT(text, position, string)
• INSERT(‘ABCDEFG’, 3, ‘XYZ’) = ‘ABXYZCDEFG’
• DELETE(text, position, length)
• DELETE(‘ABCDEFGH’, 2, 4) = ‘AFGH’
• DELETE(‘ABCDEFGH’, 0, 4) = ‘ABCDEFGH’
• DELETE(T, INDEX(T, P), LENGTH(P))
• T=‘ABCDEF’ and P=‘CD’
• INDEX(T, P)=3 and LENGTH(P)=2
• So, DELETE(T, 3, 2) = ‘ABEF’
12
WORD/TEXT PROCESSING
• REPLACE(text, pattern1, pattern2)
• REPLACE(‘XABYABZ’, ‘AB’, ‘C’) = ‘XCYABZ’
• REPLACE(‘XABYABZ’, ‘BA’, ‘D’) = ‘XABYABZ’
13
Practice Problem
Let S and T be character variables such that
S = ‘WE ARE THE PEOPLE ’
T = ‘OF THE BANGLADESH’
1. Find the length of S and T
A = SUBSTRING(S, 8, 6)
B = INSERT(A, 7, ‘BGDXY’)
C = DELETE(B, 11, 2)
D = REPLACE(C, ‘BGD’, T)
2. Find the values of A, B, C, and D
14
First Pattern Matching Algorithm
• Also known as “Slow Pattern Matching Algorithm”
• MAX Substring = LENGTH(Text) – LENGTH(Pattern) + 1
• Total number of comparisons
Problem to be solved in class
First Pattern Matching Algorithm
Consider the following pattern and text:
P = abc
T = (ab)5
• Find the total number of comparisons to find the INDEX of P in T
using “Slow Pattern Matching Algorithm”
Second Pattern Matching Algorithm
• Also known as “Fast Pattern Matching Algorithm”
Problem to be solved in class
Second Pattern Matching Algorithm
• Consider the pattern:
P = aaba
• Construct the table and the corresponding labeled directed graph
using the “fast pattern matching algorithm”
Homework
• Solve problems given in exercise
