String Algorithms
Sorting Algorithms
KMP (Knuth–Morris–Pratt) Algorithm
Core idea
Build a table of how far to "jump back" in the pattern when a mismatch happens, using the pattern's internal prefix-suffix structure. Then scan the text once, reusing previous partial matches so no character is rechecked unnecessarily.
Optimizations / notes
LPS (longest proper prefix that is also suffix) array is the key.
KMP is optimal for exact single-pattern search on static text.
For multiple patterns use Aho–Corasick instead.
Time complexity : O(n + m) where n = len(text), m = len(pattern)
Space complexity : O(m) for the LPS array
Python Code
def compute_lps(pattern):
"""Compute LPS (longest proper prefix which is also suffix) array."""
m = len(pattern)
lps = [0] * m
length = 0 # length of the previous longest prefix suffix
i = 1
# Build lps[1..m-1]
while i < m:
if pattern[i] == pattern[length]:
length += 1
lps[i] = length
i += 1
else:
if length != 0:
# fallback to previous longest prefix suffix
length = lps[length - 1]
# do not increment i here
else:
lps[i] = 0
i += 1
return lps
def kmp_search(text, pattern):
"""Return list of starting indices where pattern is found in text."""
n, m = len(text), len(pattern)
if m == 0:
return list(range(n + 1)) # empty pattern matches at all positions
lps = compute_lps(pattern)
res = []
i = j = 0 # i -> text, j -> pattern
while i < n:
if text[i] == pattern[j]:
i += 1
j += 1
if j == m:
res.append(i - j)
j = lps[j - 1] # continue searching
else:
if j != 0:
j = lps[j - 1]
else:
i += 1
return res
def main():
# Example 1
text1 = "ABABDABACDABABCABAB"
pattern1 = "ABABCABAB"
print("KMP Example 1")
print("Text:", text1)
print("Pattern:", pattern1)
print("Matches at indices:", kmp_search(text1, pattern1))
print()
# Example 2
text2 = "aaaaa"
pattern2 = "aa"
print("KMP Example 2")
print("Text:", text2)
print("Pattern:", pattern2)
print("Matches at indices:", kmp_search(text2, pattern2))
if __name__ == "__main__":
main()
Java Code
public class KMPExample {
// Compute LPS array
public static int[] computeLPS(String pat) {
int m = pat.length();
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
// KMP search
public static java.util.List<Integer> kmpSearch(String text, String pat) {
java.util.List<Integer> res = new java.util.ArrayList<>();
int n = text.length(), m = pat.length();
if (m == 0) {
for (int i = 0; i <= n; i++) res.add(i);
return res;
}
int[] lps = computeLPS(pat);
int i = 0, j = 0;
while (i < n) {
if (text.charAt(i) == pat.charAt(j)) {
i++; j++;
if (j == m) {
res.add(i - j);
j = lps[j - 1];
}
} else {
if (j != 0) j = lps[j - 1];
else i++;
}
}
return res;
}
public static void main(String[] args) {
// Example 1
String text1 = "ABABDABACDABABCABAB";
String pat1 = "ABABCABAB";
System.out.println("KMP Example 1");
System.out.println("Text: " + text1);
System.out.println("Pattern: " + pat1);
System.out.println("Matches at indices: " + kmpSearch(text1, pat1));
System.out.println();
// Example 2
String text2 = "aaaaa";
String pat2 = "aa";
System.out.println("KMP Example 2");
System.out.println("Text: " + text2);
System.out.println("Pattern: " + pat2);
System.out.println("Matches at indices: " + kmpSearch(text2, pat2));
}
}
Rabin–Karp Algorithm
Core idea
Compute a rolling numeric hash for the pattern and for each text window of the same length. Compare hashes quickly. When a hash matches, confirm by direct comparison to avoid false positives from hash collisions.
Optimizations / notes
Use a good base and a large modulus to reduce collisions.
For long patterns or many patterns, combine with multiple moduli or use double hashing.
Rabin–Karp is especially useful for multi-pattern search and plagiarism detection.
Time complexity : Average O(n + m). Worst-case O(nm) if many spurious hash collisions and naive verification costs dominate. With good hashing collisions are rare. Space complexity : O(1) (excluding input/output) or O(m) if storing patterns.
Python Code
def rabin_karp_search(text, pattern, base=256, mod=10**9+7):
"""Return list of starting indices where pattern occurs in text."""
n, m = len(text), len(pattern)
if m == 0:
return list(range(n + 1))
if m > n:
return []
# precompute base^(m-1) % mod
power = pow(base, m-1, mod)
# initial hash for pattern and first window
pat_hash = 0
win_hash = 0
for i in range(m):
pat_hash = (pat_hash * base + ord(pattern[i])) % mod
win_hash = (win_hash * base + ord(text[i])) % mod
res = []
for i in range(n - m + 1):
if pat_hash == win_hash:
# potential match, verify to avoid false positive
if text[i:i+m] == pattern:
res.append(i)
if i < n - m:
# roll: remove leading char, add next char
leading = (ord(text[i]) * power) % mod
win_hash = (win_hash - leading) % mod
win_hash = (win_hash * base + ord(text[i + m])) % mod
# ensure positive
win_hash = (win_hash + mod) % mod
return res
def main():
# Example 1
text1 = "the quick brown fox jumps over the lazy dog"
pattern1 = "quick"
print("Rabin-Karp Example 1")
print("Text:", text1)
print("Pattern:", pattern1)
print("Matches at indices:", rabin_karp_search(text1, pattern1))
print()
# Example 2 (multiple occurrences)
text2 = "abcdabcabcd"
pattern2 = "abc"
print("Rabin-Karp Example 2")
print("Text:", text2)
print("Pattern:", pattern2)
print("Matches at indices:", rabin_karp_search(text2, pattern2))
if __name__ == "__main__":
main()
Java Code
import java.util.*;
public class RabinKarpExample {
public static List<Integer> rabinKarpSearch(String text, String pat, int base, long mod) {
int n = text.length(), m = pat.length();
List<Integer> res = new ArrayList<>();
if (m == 0) {
for (int i = 0; i <= n; i++) res.add(i);
return res;
}
if (m > n) return res;
long power = 1;
for (int i = 0; i < m - 1; i++) power = (power * base) % mod;
long patHash = 0, winHash = 0;
for (int i = 0; i < m; i++) {
patHash = (patHash * base + pat.charAt(i)) % mod;
winHash = (winHash * base + text.charAt(i)) % mod;
}
for (int i = 0; i <= n - m; i++) {
if (patHash == winHash) {
if (text.substring(i, i + m).equals(pat)) res.add(i);
}
if (i < n - m) {
long leading = (text.charAt(i) * power) % mod;
winHash = (winHash - leading + mod) % mod;
winHash = (winHash * base + text.charAt(i + m)) % mod;
}
}
return res;
}
public static void main(String[] args) {
// Example 1
String text1 = "the quick brown fox jumps over the lazy dog";
String pat1 = "quick";
System.out.println("Rabin-Karp Example 1");
System.out.println("Text: " + text1);
System.out.println("Pattern: " + pat1);
System.out.println("Matches at indices: " + rabinKarpSearch(text1, pat1, 256, 1000000007L));
System.out.println();
// Example 2
String text2 = "abcdabcabcd";
String pat2 = "abc";
System.out.println("Rabin-Karp Example 2");
System.out.println("Text: " + text2);
System.out.println("Pattern: " + pat2);
System.out.println("Matches at indices: " + rabinKarpSearch(text2, pat2, 256, 1000000007L));
}
}
Boyer–Moore Algorithm
Core idea
Compare pattern from right to left and skip ahead smartly on mismatch using precomputed heuristics. Two common heuristics:
Bad-character rule: align pattern to skip past the mismatched character.
Good-suffix rule: align based on matching suffix that was found.
Optimizations / notes
Full Boyer–Moore includes both heuristics and is very fast in practice for typical texts.
Implementation below uses both heuristics in a compact form. Good-suffix preprocessing is more intricate but included for correctness.
Time complexity : Best O(n / m) average with large shifts. Worst-case O(n + m) for modern implementations with both heuristics (amortized linear). Some textbook analyses show worst-case O(nm) for naive BM if only bad-character used; combining heuristics fixes that. Space complexity : O(m + alphabet) (tables for bad char and good suffix).
Python Code
def build_bad_char_table(pattern):
"""Bad character table mapping char -> last index in pattern."""
table = {}
for i, ch in enumerate(pattern):
table[ch] = i
return table
def build_good_suffix_table(pattern):
"""
Build good suffix shift table (also called full shift).
This implementation computes two arrays: suffixes and shift.
"""
m = len(pattern)
shift = [m] * (m + 1)
suff = [0] * (m + 1)
# Compute suffixes
suff[m - 1] = m
g = m - 1
f = 0
for i in range(m - 2, -1, -1):
if i > g and suff[i + m - 1 - f] < i - g:
suff[i] = suff[i + m - 1 - f]
else:
if i < g:
g = i
f = i
while g >= 0 and pattern[g] == pattern[g + m - 1 - f]:
g -= 1
suff[i] = f - g
# Build shift
for i in range(m + 1):
shift[i] = m
j = 0
for i in range(m - 1, -1, -1):
if suff[i] == i + 1:
while j < m - 1 - i:
if shift[j] == m:
shift[j] = m - 1 - i
j += 1
for i in range(m - 1):
shift[m - 1 - suff[i]] = m - 1 - i
return shift
def boyer_moore_search(text, pattern):
"""Return list of starting indices of pattern in text using Boyer-Moore."""
n, m = len(text), len(pattern)
if m == 0:
return list(range(n + 1))
bad = build_bad_char_table(pattern)
good = build_good_suffix_table(pattern)
res = []
s = 0
while s <= n - m:
j = m - 1
while j >= 0 and pattern[j] == text[s + j]:
j -= 1
if j < 0:
res.append(s)
s += good[0] # shift so next possible match
else:
bc_shift = j - bad.get(text[s + j], -1)
gs_shift = good[j]
s += max(1, bc_shift, gs_shift)
return res
def main():
# Example 1
text1 = "HERE IS A SIMPLE EXAMPLE"
pattern1 = "EXAMPLE"
print("Boyer-Moore Example 1")
print("Text:", text1)
print("Pattern:", pattern1)
print("Matches at indices:", boyer_moore_search(text1, pattern1))
print()
# Example 2 (multiple and overlapping)
text2 = "ABAAABCD"
pattern2 = "ABA"
print("Boyer-Moore Example 2")
print("Text:", text2)
print("Pattern:", pattern2)
print("Matches at indices:", boyer_moore_search(text2, pattern2))
if __name__ == "__main__":
main()
Java Code
import java.util.*;
public class BoyerMooreExample {
// Build bad character table
public static Map<Character, Integer> buildBadCharTable(String pat) {
Map<Character, Integer> table = new HashMap<>();
for (int i = 0; i < pat.length(); i++) {
table.put(pat.charAt(i), i);
}
return table;
}
// Build good suffix shift table
public static int[] buildGoodSuffixTable(String pat) {
int m = pat.length();
int[] shift = new int[m + 1];
int[] suff = new int[m + 1];
// compute suff
suff[m - 1] = m;
int g = m - 1;
int f = 0;
for (int i = m - 2; i >= 0; i--) {
if (i > g && suff[i + m - 1 - f] < i - g) {
suff[i] = suff[i + m - 1 - f];
} else {
if (i < g) g = i;
f = i;
while (g >= 0 && pat.charAt(g) == pat.charAt(g + m - 1 - f)) g--;
suff[i] = f - g;
}
}
Arrays.fill(shift, m);
int j = 0;
for (int i = m - 1; i >= 0; i--) {
if (suff[i] == i + 1) {
while (j < m - 1 - i) {
if (shift[j] == m) shift[j] = m - 1 - i;
j++;
}
}
}
for (int i = 0; i < m - 1; i++) {
shift[m - 1 - suff[i]] = m - 1 - i;
}
return shift;
}
public static List<Integer> boyerMooreSearch(String text, String pat) {
int n = text.length(), m = pat.length();
List<Integer> res = new ArrayList<>();
if (m == 0) {
for (int i = 0; i <= n; i++) res.add(i);
return res;
}
Map<Character, Integer> bad = buildBadCharTable(pat);
int[] good = buildGoodSuffixTable(pat);
int s = 0;
while (s <= n - m) {
int j = m - 1;
while (j >= 0 && pat.charAt(j) == text.charAt(s + j)) j--;
if (j < 0) {
res.add(s);
s += good[0];
} else {
int bcShift = j - bad.getOrDefault(text.charAt(s + j), -1);
int gsShift = good[j];
s += Math.max(1, Math.max(bcShift, gsShift));
}
}
return res;
}
public static void main(String[] args) {
// Example 1
String text1 = "HERE IS A SIMPLE EXAMPLE";
String pat1 = "EXAMPLE";
System.out.println("Boyer-Moore Example 1");
System.out.println("Text: " + text1);
System.out.println("Pattern: " + pat1);
System.out.println("Matches at indices: " + boyerMooreSearch(text1, pat1));
System.out.println();
// Example 2
String text2 = "ABAAABCD";
String pat2 = "ABA";
System.out.println("Boyer-Moore Example 2");
System.out.println("Text: " + text2);
System.out.println("Pattern: " + pat2);
System.out.println("Matches at indices: " + boyerMooreSearch(text2, pat2));
}
}
Z Algorithm
Core idea
Compute for each position in a string the length of the longest substring starting there that matches the prefix. For pattern search, form string = pattern + '$' + text and compute Z array. Wherever a Z value equals pattern length is a match.
Optimizations / notes
Linear time via maintaining a [L, R] window of the rightmost segment matched to prefix.
Z algorithm is very fast for many pattern-processing tasks, e.g., computing runs, borders, or multiple pattern searches via concatenation.
Time complexity : O(n + m) when used for pattern search (linear overall)
Space complexity : O(n + m) for concatenated string and Z array (or O(n) for Z alone)
Python Code
def compute_z(s):
"""Compute Z array for string s in O(len(s))."""
n = len(s)
z = [0] * n
l = r = 0
for i in range(1, n):
if i <= r:
z[i] = min(r - i + 1, z[i - l])
while i + z[i] < n and s[z[i]] == s[i + z[i]]:
z[i] += 1
if i + z[i] - 1 > r:
l, r = i, i + z[i] - 1
z[0] = n
return z
def z_search(text, pattern):
"""Return list of starting indices where pattern found using Z algorithm."""
if len(pattern) == 0:
return list(range(len(text) + 1))
concat = pattern + "$" + text
z = compute_z(concat)
res = []
m = len(pattern)
for i in range(m + 1, len(concat)):
if z[i] == m:
res.append(i - m - 1) # index in text
return res
def main():
# Example 1
text1 = "abxabcabcaby"
pattern1 = "abcaby"
print("Z-Algorithm Example 1")
print("Text:", text1)
print("Pattern:", pattern1)
print("Matches at indices:", z_search(text1, pattern1))
print()
# Example 2
text2 = "aaaaa"
pattern2 = "aa"
print("Z-Algorithm Example 2")
print("Text:", text2)
print("Pattern:", pattern2)
print("Matches at indices:", z_search(text2, pattern2))
if __name__ == "__main__":
main()
Java Code
import java.util.*;
public class ZAlgorithmExample {
public static int[] computeZ(String s) {
int n = s.length();
int[] z = new int[n];
int l = 0, r = 0;
for (int i = 1; i < n; i++) {
if (i <= r) z[i] = Math.min(r - i + 1, z[i - l]);
while (i + z[i] < n && s.charAt(z[i]) == s.charAt(i + z[i])) z[i]++;
if (i + z[i] - 1 > r) {
l = i; r = i + z[i] - 1;
}
}
z[0] = n;
return z;
}
public static List<Integer> zSearch(String text, String pat) {
List<Integer> res = new ArrayList<>();
if (pat.length() == 0) {
for (int i = 0; i <= text.length(); i++) res.add(i);
return res;
}
String concat = pat + "$" + text;
int[] z = computeZ(concat);
int m = pat.length();
for (int i = m + 1; i < concat.length(); i++) {
if (z[i] == m) res.add(i - m - 1);
}
return res;
}
public static void main(String[] args) {
// Example 1
String text1 = "abxabcabcaby";
String pat1 = "abcaby";
System.out.println("Z-Algorithm Example 1");
System.out.println("Text: " + text1);
System.out.println("Pattern: " + pat1);
System.out.println("Matches at indices: " + zSearch(text1, pat1));
System.out.println();
// Example 2
String text2 = "aaaaa";
String pat2 = "aa";
System.out.println("Z-Algorithm Example 2");
System.out.println("Text: " + text2);
System.out.println("Pattern: " + pat2);
System.out.println("Matches at indices: " + zSearch(text2, pat2));
}
}
Aho–Corasick Algorithm (Multiple Pattern String Matching)
Core Idea
The Aho–Corasick algorithm efficiently finds all occurrences of multiple patterns in a text at once. It combines Trie + Failure Links (like KMP’s partial match table).
Trie step: insert all patterns.
Failure link step: connect each node to the longest proper suffix that is also a prefix.
Search step: process text in linear time using these links.
This achieves O(N + M + Z) time where
N = length of text,
M = total length of all patterns,
Z = number of matches.
Python Code
from collections import deque, defaultdict
class AhoCorasick:
def __init__(self):
self.trie = [{}]
self.output = [set()]
self.fail = [0]
def insert(self, word):
node = 0
for ch in word:
if ch not in self.trie[node]:
self.trie[node][ch] = len(self.trie)
self.trie.append({})
self.output.append(set())
self.fail.append(0)
node = self.trie[node][ch]
self.output[node].add(word)
def build(self):
q = deque()
for ch, nxt in self.trie[0].items():
q.append(nxt)
self.fail[nxt] = 0
while q:
r = q.popleft()
for ch, nxt in self.trie[r].items():
q.append(nxt)
f = self.fail[r]
while f and ch not in self.trie[f]:
f = self.fail[f]
self.fail[nxt] = self.trie[f].get(ch, 0)
self.output[nxt] |= self.output[self.fail[nxt]]
def search(self, text):
node = 0
result = []
for i, ch in enumerate(text):
while node and ch not in self.trie[node]:
node = self.fail[node]
node = self.trie[node].get(ch, 0)
for pat in self.output[node]:
result.append((i - len(pat) + 1, pat))
return result
if __name__ == "__main__":
ac = AhoCorasick()
patterns = ["he", "she", "hers", "his"]
for p in patterns:
ac.insert(p)
ac.build()
text = "ushers"
res = ac.search(text)
print("Text:", text)
print("Matches found:", res)
# Second example
ac2 = AhoCorasick()
for p in ["ab", "bc", "abc"]:
ac2.insert(p)
ac2.build()
print(ac2.search("abcbcabc"))
Java Code
import java.util.*;
class AhoCorasick {
static class Node {
Map<Character, Node> next = new HashMap<>();
Node fail;
List<String> out = new ArrayList<>();
}
private Node root = new Node();
public void insert(String word) {
Node cur = root;
for (char ch : word.toCharArray()) {
cur = cur.next.computeIfAbsent(ch, k -> new Node());
}
cur.out.add(word);
}
public void build() {
Queue<Node> q = new ArrayDeque<>();
for (Node node : root.next.values()) {
node.fail = root;
q.add(node);
}
while (!q.isEmpty()) {
Node r = q.poll();
for (var e : r.next.entrySet()) {
char ch = e.getKey();
Node nxt = e.getValue();
q.add(nxt);
Node f = r.fail;
while (f != null && !f.next.containsKey(ch)) f = f.fail;
nxt.fail = (f == null) ? root : f.next.get(ch);
nxt.out.addAll(nxt.fail.out);
}
}
}
public List<String> search(String text) {
List<String> res = new ArrayList<>();
Node node = root;
for (char ch : text.toCharArray()) {
while (node != root && !node.next.containsKey(ch))
node = node.fail;
node = node.next.getOrDefault(ch, root);
res.addAll(node.out);
}
return res;
}
public static void main(String[] args) {
AhoCorasick ac = new AhoCorasick();
for (String p : List.of("he", "she", "his", "hers")) ac.insert(p);
ac.build();
System.out.println(ac.search("ushers"));
AhoCorasick ac2 = new AhoCorasick();
for (String p : List.of("ab", "bc", "abc")) ac2.insert(p);
ac2.build();
System.out.println(ac2.search("abcbcabc"));
}
}
Time Complexity: O(N + M + Z)
Space Complexity: O(M × alphabet size)
Manacher’s Algorithm (Longest Palindromic Substring)
Core Idea
Expands around every character in linear time by avoiding redundant comparisons.
It transforms the string (using # between letters) to handle even/odd cases uniformly, then expands palindromes using a mirror property around a center.
Python Code
def manacher(s):
t = "#" + "#".join(s) + "#"
n = len(t)
P = [0]*n
center = right = 0
max_len = 0
center_index = 0
for i in range(n):
mirror = 2*center - i
if i < right:
P[i] = min(right - i, P[mirror])
while i - 1 - P[i] >= 0 and i + 1 + P[i] < n and t[i + 1 + P[i]] == t[i - 1 - P[i]]:
P[i] += 1
if i + P[i] > right:
center, right = i, i + P[i]
if P[i] > max_len:
max_len, center_index = P[i], i
start = (center_index - max_len) // 2
return s[start:start + max_len]
if __name__ == "__main__":
print(manacher("babad")) # aba or bab
print(manacher("cbbd")) # bb
Java Code
public class Manacher {
public static String longestPalindrome(String s) {
StringBuilder t = new StringBuilder("#");
for (char c : s.toCharArray()) t.append(c).append("#");
int n = t.length();
int[] P = new int[n];
int C = 0, R = 0, maxLen = 0, centerIndex = 0;
for (int i = 0; i < n; i++) {
int mirror = 2*C - i;
if (i < R) P[i] = Math.min(R - i, P[mirror]);
while (i - 1 - P[i] >= 0 && i + 1 + P[i] < n && t.charAt(i + 1 + P[i]) == t.charAt(i - 1 - P[i]))
P[i]++;
if (i + P[i] > R) { C = i; R = i + P[i]; }
if (P[i] > maxLen) { maxLen = P[i]; centerIndex = i; }
}
int start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}
public static void main(String[] args) {
System.out.println(longestPalindrome("babad"));
System.out.println(longestPalindrome("cbbd"));
}
}
Time Complexity: O(N)
Space Complexity: O(N)
Huffman Encoding Algorithm
Core Idea
Used for lossless data compression.
Build a binary tree where frequent characters have shorter codes.
Count frequencies.
Build min-heap of nodes.
Merge smallest two nodes until one remains (root).
Traverse to assign binary codes.
Python Code
import heapq
class Node:
def __init__(self, ch, freq):
self.ch = ch
self.freq = freq
self.left = self.right = None
def __lt__(self, other):
return self.freq < other.freq
def build_huffman(text):
freq = {}
for c in text:
freq[c] = freq.get(c, 0) + 1
heap = [Node(ch, fr) for ch, fr in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
l = heapq.heappop(heap)
r = heapq.heappop(heap)
merged = Node(None, l.freq + r.freq)
merged.left, merged.right = l, r
heapq.heappush(heap, merged)
return heap[0]
def generate_codes(node, code="", mapping={}):
if node:
if node.ch is not None:
mapping[node.ch] = code
generate_codes(node.left, code + "0", mapping)
generate_codes(node.right, code + "1", mapping)
return mapping
if __name__ == "__main__":
text = "hello world"
root = build_huffman(text)
codes = generate_codes(root)
print("Huffman Codes:", codes)
encoded = "".join(codes[c] for c in text)
print("Encoded:", encoded)
print("Decoded:", text) # demonstration
Java Code
import java.util.*;
class Huffman {
static class Node implements Comparable<Node> {
char ch; int freq;
Node left, right;
Node(char c, int f) { ch=c; freq=f; }
public int compareTo(Node o){ return freq - o.freq; }
}
static Node buildTree(String text) {
Map<Character,Integer> freq = new HashMap<>();
for(char c:text.toCharArray()) freq.put(c, freq.getOrDefault(c,0)+1);
PriorityQueue<Node> pq = new PriorityQueue<>();
for(var e:freq.entrySet()) pq.add(new Node(e.getKey(), e.getValue()));
while(pq.size()>1){
Node l=pq.poll(), r=pq.poll();
Node p=new Node('\0', l.freq+r.freq);
p.left=l; p.right=r; pq.add(p);
}
return pq.poll();
}
static void genCodes(Node root, String code, Map<Character,String> map){
if(root==null) return;
if(root.ch!='\0') map.put(root.ch, code);
genCodes(root.left, code+"0", map);
genCodes(root.right, code+"1", map);
}
public static void main(String[] args){
String text="hello world";
Node root=buildTree(text);
Map<Character,String> map=new HashMap<>();
genCodes(root,"",map);
System.out.println("Codes: "+map);
StringBuilder enc=new StringBuilder();
for(char c:text.toCharArray()) enc.append(map.get(c));
System.out.println("Encoded: "+enc);
System.out.println("Decoded: "+text);
}
}
Time Complexity: O(N log N)
Space Complexity: O(N)
Trie Operations (Insert/Search)
Core Idea
Trie (Prefix Tree) stores words character by character.
Efficient for prefix queries and dictionary lookups.
Each node represents a prefix, and a boolean marks the end of a word.
Python Code
class TrieNode:
def __init__(self):
self.children = {}
self.end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word):
node = self.root
for c in word:
node = node.children.setdefault(c, TrieNode())
node.end = True
def search(self, word):
node = self.root
for c in word:
if c not in node.children:
return False
node = node.children[c]
return node.end
if __name__ == "__main__":
trie = Trie()
for word in ["apple", "app", "bat"]:
trie.insert(word)
print(trie.search("app"))
print(trie.search("batman"))
Java Code
import java.util.*;
class Trie {
static class Node {
Map<Character, Node> children = new HashMap<>();
boolean end;
}
private Node root = new Node();
public void insert(String word) {
Node node = root;
for (char c : word.toCharArray())
node = node.children.computeIfAbsent(c, k -> new Node());
node.end = true;
}
public boolean search(String word) {
Node node = root;
for (char c : word.toCharArray()) {
if (!node.children.containsKey(c)) return false;
node = node.children.get(c);
}
return node.end;
}
public static void main(String[] args) {
Trie trie = new Trie();
for (String s : List.of("apple", "app", "bat")) trie.insert(s);
System.out.println(trie.search("app"));
System.out.println(trie.search("batman"));
}
}
Time Complexity:
Insert: O(L)
Search: O(L)
(L = length of word)
Space Complexity: O(ALPHABET × total chars)
Comments
Join the discussionNo comments yet. Be the first to comment.
