Naive String-Matching Algorithm

 This is simple and efficient brute force approach. It

compares the first character of pattern with
searchable text. If a match is found, pointers in both
strings are advanced. If a match is not found, the
pointer to text is incremented and pointer of the
pattern is reset. This process is repeated till the end of
the text.
 The naïve approach does not require any pre-
processing. Given text T and pattern P, it directly
starts comparing both strings character by character.
 After each comparison, it shifts pattern string one
position to the right.
 Following example illustrates the working of naïve
string matching algorithm. Here,
T = PLANINGANDANALYASIS and P = AND
 Here, ti and pj are indices of text and pattern
respectively.

Step 1: T[1] ≠ P[1], so advance text pointer, i.e. ti++.

Step 2 : T[2] ≠ P[1], so advance text pointers i.e. ti++

Step 3 : T[3] = P[1], so advance both pointers i.e. ti++,
pj++

Step 4 : T[4] = P[2], so advance both pointers, i.e. ti++,

pj++

Step 5 : T[5] ≠ P[3], so advance text pointer and reset

pattern pointer, i.e. ti++, pj = 1
Step 6 : T[6] ≠ P[1], so advance text pointer, i.e. ti++

Step 7: T[7] ≠ P[1], so advance text pointer i.e. ti++

Step 8 : T[8] = P[1], so advance both pointers, i.e. ti++,

pj++
Step 9 : T[9] = P[2], so advance both pointers, i.e. ti++,
pj++

Step 10 : T[10] = P[3], so advance both pointers, i.e. ti++,

pj++

This process continues till the possible comparison in the

text string.
Algorithm
Algorithm NAÏVE_STRING_MATCHING(T, P)
// T is the text string of length n
// P is the pattern of length m
for i ← 0 to n – m do
if P[1… m] == T[i+1…i+m] them
print “Match Found”
end
end
Complexity Analysis
There are two cases of consideration :
(i) Pattern found
 The worst case occurs when the pattern is at last
position and there are spurious hits all the way.
Example, T = AAAAAAAAAAB, P = AAAB.
 To move pattern one position right, m comparisons are
made. Searchable text in T has a length (n – m).
Hence, in worst case algorithm runs in O(m*(n – m))
time.
(ii) Pattern not found
 In the best case, the searchable text does not contain
any of the prefixes of the pattern. Only one
comparison requires moving pattern one position
right.
Example, T = ABABCDBCAC, P = XYXZ. The algorithm
does O(n – m) comparisons.
 In the worst case, first (m – 1) characters of pattern
and text are matched and only last character does not
match.
Example, T = AAAAAAAAAAAAC, P = AAAAB. Algorithm
takes O(m*(n – m)) time.

Rabin-Karp String Matching Algorithm

Why Use Rabin-Karp?
 Efficient for searching multiple patterns
simultaneously.
 Uses hashing to quickly check candidate substrings.
 Avoids redundant comparisons seen in naive methods.
  Well-suited for plagiarism detection and digital
forensics.

The Rabin-Karp algorithm is used for string

matching — that means finding whether a pattern
(substring) exists in a main text (string).
It uses a hashing technique to compare strings fast, instead
of checking characters one by one like the Naïve algorithm.
Instead of directly comparing the pattern with every
substring of the text,
Rabin-Karp converts both the pattern and substrings of the
text into hash values.
Then it compares those hash values.
If the hash values are same, only then it checks characters
one by one (to confirm it’s not a false match).
Example:
Let’s find pattern = “ABC” in text = “ABCDABC”
Step 1: Assign numeric values to letters (for simplicity)
A = 1, B = 2, C = 3, D = 4
Step 2: Calculate hash of pattern and substrings
Let’s use a simple hash formula for understanding:
hash = sum of character values
Pattern: “ABC”
→1+2+3=6
Now, check substrings of text of length 3 (same as
pattern):
Substr Matches pattern
Hash
ing hash (6)?
ABC 1+2+3 Yes
Substr Matches pattern
Hash
ing hash (6)?
=6
2+3+4
BCD No
=9
3+4+1
CDA No
=8
4+1+2
DAB No
=7
1+2+3
ABC Yes
=6
Matches found at positions 0 and 4
Step 3: Confirm matches
Now, we compare the actual strings only for matching hash
values.
At index 0: "ABC" == "ABC" → Match
At index 4: "ABC" == "ABC" → Match
So pattern found at index 0 and 4.
How it becomes efficient:
Instead of re-computing hash for each substring from
scratch,
we can recalculate it quickly using the previous hash (this
is called rolling hash).
Example:
For text “ABCDABC”
Hash(ABC) = 6
To get Hash(BCD),
Remove A (1), add D (4):
6-1+4=9
→ So we get next hash in O(1) time.
That’s why Rabin-Karp is faster than the naïve method
when checking multiple patterns or large texts.
Algorithm Steps:
1. Compute hash of pattern (p)
2. Compute hash of first window (substring) in text
3. Slide the window one by one through text
4. For each new window:
o Update hash efficiently (rolling hash)
o If hashes match → compare actual strings
5. If strings match → record index
Time Complexity:
 Average case: O(n + m)
 Worst case: O(nm) (when many hash collisions occur)
Applications:
 Search for a word in large documents
 Detect plagiarism
 Search keywords in web pages
 DNA sequence matching

Knuth-Morris-Pratt Algorithm
The KMP algorithm is used to find a pattern in a text
efficiently.
It avoids checking the same characters again and again
when a mismatch happens — this makes it faster than the
normal (naïve) method.
Prefix = starting part of a string.
Suffix = ending part of a string.
Example:
For the word "ABAB"
 Prefixes: A, AB, ABA
 Suffixes: B, AB, BAB
Notice: both “AB” appear as prefix and suffix — that’s
important!
What is LPS Value?
LPS = Longest Proper Prefix which is also Suffix.
It tells — “up to this point in the pattern, how many
characters at the start are same as characters at the end.”
We calculate this for each position in the pattern.
This LPS helps the algorithm decide how much of the
pattern we can reuse after a mismatch.
Let’s take pattern = "AAAB"
We’ll calculate LPS for each char

Inde Pattern up to this LPS

Explanation
x point value
0 A 0 No proper prefix/suffix
1 AA 1 “A” is both prefix & suffix
2 AAA 2 “AA” is both prefix & suffix
3 AAAB 0 No prefix = suffix

So, LPS = [0, 1, 2, 0]

This means:
 After matching first 3 letters and getting mismatch on
4th,
 we don’t need to start from the beginning — we can
reuse 2 characters (because LPS[2] = 2).
Algorithm:
1. Define a prefix function.
2. Slide the pattern over the text for comparison.
3. If all the characters match, we have found a
match.
4. If not, use the prefix function to skip the
unnecessary comparisons. If the LPS value of
previous character from the mismatched
character is '0', then start comparison from index
0 of pattern with the next character in the text.
However, if the LPS value is more than '0', start
the comparison from index value equal to LPS
value of the previously mismatched character.

Applications of DSA:
Social Network Graph Analysis:
Ever wonder how Facebook knows who your mutual friends
are, or how Google Maps finds the fastest route through a
maze of streets? The secret lies in the elegant and
surprisingly powerful world of graphs - a way of seeing
connections that's transforming everything from social lives
to fighting pandemics.
In social networking sites like Facebook, Instagram,
LinkedIn, or Twitter, there are millions of users
connected to each other in various ways — as friends,
followers, or connections.
To manage and analyze this large amount of relationship
data, Data Structures and Algorithms (DSA) —
especially Graphs — play an important role.
How Graphs Represent a Social Network
A graph consists of:
 Vertices (Nodes) → represent users or profiles
 Edges (Links) → represent relationships (friendship,
follow, connection)
Here:
 A, B, C, D, E are users
 The lines (edges) show connections
(friendship/followers)
1. Friend Recommendation System
Social media platforms use Graph Traversal Algorithms
like Breadth-First Search (BFS) to find mutual friends or
connections and recommend new friends.
Example:
 If A is friends with B, and B is friends with C, then C
can be suggested as a friend to A (since they have a
mutual friend B).
  This idea is also used on LinkedIn (“People you may
know”).
BFS to explore nearby connections
Hash Maps / Sets to quickly check existing connections
2. Community Detection (Finding Groups or
Clusters)
A community is a group of users who are more connected
to each other than to others.
DSA helps identify these groups using Connected
Components or DFS (Depth First Search).
DFS or Union-Find (Disjoint Set) to find clusters.
Uses
Facebook identifies groups with similar interests.
Instagram finds users in the same local circle.
3. Influencer or Important User Detection
Some users are more influential — they have many
followers or connections.
We can detect them using Graph Centrality Algorithms
or Degree Counting.
User A has the most outgoing connections → A is
influential.
Degree Centrality: Count number of connections
PageRank Algorithm (used by Google, Twitter) to
measure influence.
Uses
 Twitter identifies verified or trending accounts.
 Instagram suggests “Top Influencers” in your area.
4. Finding the Shortest Path (Degree of
Separation)
Shows how closely two people are connected.
Used to find “how many steps away” one user is from
another.
Shortest path from A to D = 3 connections (A-B-C-D)
 BFS for unweighted connections
 Dijkstra’s Algorithm if each edge has a weight (like
communication strength or interaction frequency)
Use:
LinkedIn shows “You are 3rd connection to this person.”
Facebook shows mutual friends or degrees of separation.
5. News Feed Ranking and Recommendations
When you open your feed, posts are shown in order of
importance — likes, shares, and comments.
Data structures like Heaps (Priority Queues) and Hash
Tables help rank and sort this data quickly.
Example:
Suppose 3 posts have likes:
Post A – 500 likes, Post B – 200 likes, Post C – 800 likes
A max-heap can be used to show posts in order: C → A →
B.
Use:
Instagram and Facebook show posts by importance, not by
time.

YouTube suggests videos using ranking + recommendation

systems.
6. Detecting Fake or Spam Accounts
Fake accounts often have unusual connection patterns.
Graph traversal and pattern matching algorithms help
detect them.
Example:
If a user follows 1000 people but is followed by none, it
may be suspicious.
Graph analysis detects such patterns.
DFS / BFS to check connectivity
Pattern detection algorithms to find anomalies
Use:
Twitter and Facebook detect bot or spam networks.
7. Information or Message Spreading
When a user posts something, it spreads like waves to
connected users — just like Graph Traversal (BFS).
Example:
If A shares a post:
A → B, C
B→D
C→E
Then the post spreads to D and E via B and C.
Real-life Use:
Facebook post sharing
WhatsApp message forwarding analysis
1) What is an AI Search Algorithm?
An AI search algorithm is a method to explore many
possible states (positions, configurations, paths) to find one
that meets a goal (shortest path, solved puzzle, winning
move). We model the problem as a graph or tree of
states; search algorithms traverse that graph to find the
goal.
2) where DSA fits
 Graph / tree = main data structure to represent
states and transitions.
 Queues, stacks, priority queues, hash sets =
used to store frontier/open nodes and visited/closed
nodes.
 Efficient operations on these structures are crucial for
speed and memory.
3) Main categories of search
A. Uninformed (blind) search
A. Breadth-First Search (BFS)
B. Depth-First Search (DFS)
B Informed (heuristic) search
Greedy Best-First Search
 Expand node with smallest h(n) (looks promising).
 Priority queue by h(n).
 Fast but not optimal or complete (may get trapped).
Use: Quick approximations, pathfinding where speed
matters more than optimality.
C. Local search & optimization (no full state-space
kept)
Used for optimization or very large search spaces.
Hill Climbing
 Move to neighbor with better value until no
improvement.
 Gets stuck in local maxima.
 Use: Simple optimization problems.
Simulated Annealing
  Like hill climbing but sometimes accepts worse moves
to escape local maxima; acceptance probability
decreases over time.
 Use: Large combinatorial optimization.
Genetic Algorithms (GA)
 Population of candidate solutions → selection,
crossover, mutation → new generation.
 Use: Evolving good solutions where gradient isn’t
available (design, optimization).
Beam Search
 Like BFS but keep only top-k best nodes at each depth
(beam width).
 Use: NLP tasks (machine translation, speech
recognition) as a speed/memory tradeoff.
 Example: Beam search in seq2seq—keep top 5 partial
sentences during decoding.
D. Adversarial Search (games)
Used when an opponent is playing against you.
Minimax & Alpha-Beta Pruning
 Build game tree; minimax chooses moves to maximize
your worst-case outcome. Alpha-beta prunes branches
that won’t affect final decision.
 Data structures: Tree, recursion, simple numeric
values.
 Use: Chess, tic-tac-toe, checkers (with evaluation
functions for leaf nodes).
4) Heuristics — admissible & consistent
 Admissible: h(n) ≤ true minimal cost from n to goal.
Guarantees A* optimality.
  Consistent (monotone): For every edge (n→n’): h(n)
≤ cost(n,n’) + h(n’). If consistent, f-values along path
are non-decreasing; simplifies implementation (closed
set safe).
 Designing heuristics: Use relaxed problem solutions
(easier version of the problem) as heuristic; e.g.,
ignoring obstacles or movement costs.
Example heuristics
 Grid 4-direction: Manhattan distance = |x1-x2| + |y1-
y2|
 8-puzzle: sum of Manhattan distances of tiles from
their goal positions (admissible).