[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":92,"_72":93,"_35":94},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":19,"_64":65,"_66":67,"_68":69,"_70":71},"id",37,"title","String Searching Algorithms","slug","algorithms-part-10-string-searching","excerpt","Master KMP, Rabin-Karp, Boyer-Moore, and Aho-Corasick for finding patterns in text. Solve multiple pattern matching problems like log analysis.","# Algorithms Compendium Part 10: String Searching Algorithms\n\nString searching - finding a pattern within text - is one of the most common operations in computing. From text editors to log analysis, from DNA sequencing to spam filtering, efficient string matching is critical. The naive O(nm) approach becomes prohibitive for large texts. This article covers four major algorithms that achieve O(n+m) performance through clever preprocessing.\n\n## 📋 At a Glance\n\n| Algorithm | Preprocessing | Search | Best For |\n|-----------|---------------|--------|----------|\n| Naive | O(1) | O(nm) | Short patterns, small texts |\n| KMP | O(m) | O(n) | Single pattern, streaming |\n| Rabin-Karp | O(m) | O(n) avg | Multiple patterns, plagiarism detection |\n| Boyer-Moore | O(m + σ) | O(n/m) best | Long patterns, large alphabets |\n| Aho-Corasick | O(Σm) | O(n + z) | Multiple patterns simultaneously |\n\nWhere n = text length, m = pattern length, σ = alphabet size, z = number of matches\n\n---\n\n## 🎯 What You'll Learn\n\nAfter reading this article, you will be able to:\n\n- **Implement KMP** with proper failure function construction\n- **Apply Rabin-Karp** for multiple pattern matching\n- **Use Boyer-Moore** for practical high-performance search\n- **Build Aho-Corasick automaton** for simultaneous multi-pattern search\n- **Choose the right algorithm** based on pattern count and size\n- **Understand Java's String.indexOf()** implementation\n\n---\n\n## 🔥 Production Story: The Log Analysis Nightmare\n\nA security team needed to scan 500GB of server logs daily for 200 suspicious patterns (SQL injection attempts, XSS payloads, known attack signatures).\n\n```java\n// ❌ Initial approach: Naive search for each pattern\npublic class LogScanner {\n private final List patterns;\n\n public List scanFile(Path logFile) throws IOException {\n List matches = new ArrayList<>();\n List lines = Files.readAllLines(logFile);\n\n for (String line : lines) {\n for (String pattern : patterns) {\n int idx = line.indexOf(pattern); // O(n * m) per pattern!\n if (idx >= 0) {\n matches.add(new Match(line, pattern, idx));\n }\n }\n }\n return matches;\n }\n}\n// Time for 500GB with 200 patterns: ~18 hours\n```\n\n**Analysis:**\n- 500GB ≈ 5 billion characters\n- 200 patterns × average 20 chars = 4000 chars to check per position\n- Naive: O(n × m × p) where p = number of patterns\n- Total operations: 5B × 20 × 200 = 20 quadrillion operations!\n\n**The optimization:**\n\n```java\n// ✅ Aho-Corasick: Search all patterns in single pass\npublic class OptimizedLogScanner {\n private final AhoCorasick automaton;\n\n public OptimizedLogScanner(List patterns) {\n this.automaton = new AhoCorasick(patterns);\n }\n\n public List scanFile(Path logFile) throws IOException {\n List matches = new ArrayList<>();\n\n try (BufferedReader reader = Files.newBufferedReader(logFile)) {\n String line;\n while ((line = reader.readLine()) != null) {\n // Single pass through line finds ALL pattern matches\n matches.addAll(automaton.search(line));\n }\n }\n return matches;\n }\n}\n// Time for 500GB with 200 patterns: ~25 minutes\n```\n\n**Results:**\n- Naive: 18 hours\n- Aho-Corasick: 25 minutes\n- **43x faster** - reduced from overnight job to lunch break\n\n**The lesson:** When searching for multiple patterns, building a combined automaton once pays off massively compared to searching each pattern separately.\n\n---\n\n## 🧠 Mental Model: String Search Algorithm Selection\n\n```text\nSTRING SEARCH DECISION TREE\n━━━━━━━━━━━━━━━━━━━━━━━━━━━\n\nHow many patterns?\n│\n├── Single pattern\n│ │\n│ ├── Pattern short (< 5 chars)?\n│ │ └── Naive / String.indexOf()\n│ │\n│ ├── Need guaranteed O(n)?\n│ │ └── KMP\n│ │\n│ ├── Large alphabet + long pattern?\n│ │ └── Boyer-Moore\n│ │\n│ └── Approximate matching needed?\n│ └── Rabin-Karp (with hash tolerance)\n│\n└── Multiple patterns\n │\n ├── Few patterns (< 10)?\n │ └── Run single-pattern algo for each\n │\n ├── Many patterns, same-time search?\n │ └── Aho-Corasick\n │\n └── Patterns are subsets of each other?\n └── Aho-Corasick (handles naturally)\n```\n\n---\n\n## 🔬 Deep Dive: Naive String Search\n\n### The Algorithm\n\n```java\npublic class NaiveSearch {\n /**\n * Naive string search - check every position.\n *\n * Time: O(n * m) worst case\n * Space: O(1)\n */\n public static int search(String text, String pattern) {\n int n = text.length();\n int m = pattern.length();\n\n for (int i = 0; i <= n - m; i++) {\n int j = 0;\n while (j < m && text.charAt(i + j) == pattern.charAt(j)) {\n j++;\n }\n if (j == m) {\n return i; // Found at position i\n }\n }\n return -1; // Not found\n }\n\n /**\n * Find all occurrences.\n */\n public static List searchAll(String text, String pattern) {\n List positions = new ArrayList<>();\n int n = text.length();\n int m = pattern.length();\n\n for (int i = 0; i <= n - m; i++) {\n int j = 0;\n while (j < m && text.charAt(i + j) == pattern.charAt(j)) {\n j++;\n }\n if (j == m) {\n positions.add(i);\n }\n }\n return positions;\n }\n}\n```\n\n### Why Naive Is Slow\n\n```text\nNAIVE SEARCH WORST CASE\n━━━━━━━━━━━━━━━━━━━━━━━\n\nText: AAAAAAAAAAAAAAAB\nPattern: AAAAB\n\nPosition 0: AAAAA != AAAAB (matched 4, failed at 5th)\nPosition 1: AAAAA != AAAAB (matched 4, failed at 5th)\nPosition 2: AAAAA != AAAAB (matched 4, failed at 5th)\n...\nPosition 11: AAAAB == AAAAB (found!)\n\nTotal comparisons: 11 × 5 = 55 (O(n × m))\n\nThe problem: After failing at position 0, we learned nothing!\nWe matched \"AAAA\" but threw away that information.\n```\n\n---\n\n## 🔬 Deep Dive: KMP (Knuth-Morris-Pratt)\n\n### The Key Insight\n\nWhen a mismatch occurs, we've already matched some prefix of the pattern. KMP uses this information to skip ahead intelligently.\n\n```text\nKMP INSIGHT\n━━━━━━━━━━━\n\nText: ABCABCABD\nPattern: ABCABD\n\nPosition 0:\n A B C A B C A B D\n A B C A B D\n ^ mismatch at position 5\n\nNaive: Start over at position 1\nKMP: We matched \"ABCAB\". The suffix \"AB\" is also a prefix!\n Skip to align that prefix with what we've seen.\n\n A B C A B C A B D\n A B C A B D ← Skip ahead, reuse \"AB\" match\n ^ continue from here\n```\n\n### The Failure Function (LPS Array)\n\nThe failure function `lps[i]` = length of longest proper prefix of `pattern[0..i]` which is also a suffix.\n\n```java\npublic class KMP {\n /**\n * Build the LPS (Longest Proper Prefix which is also Suffix) array.\n * Also called \"failure function\" or \"partial match table\".\n *\n * Time: O(m)\n * Space: O(m)\n */\n public static int[] buildLPS(String pattern) {\n int m = pattern.length();\n int[] lps = new int[m];\n lps[0] = 0; // First character has no proper prefix\n\n int len = 0; // Length of previous longest prefix suffix\n int i = 1;\n\n while (i < m) {\n if (pattern.charAt(i) == pattern.charAt(len)) {\n len++;\n lps[i] = len;\n i++;\n } else {\n if (len != 0) {\n // Try shorter prefix\n len = lps[len - 1];\n // Don't increment i here\n } else {\n lps[i] = 0;\n i++;\n }\n }\n }\n\n return lps;\n }\n\n /**\n * KMP search algorithm.\n *\n * Time: O(n + m)\n * Space: O(m) for LPS array\n */\n public static int search(String text, String pattern) {\n if (pattern.isEmpty()) return 0;\n if (text.isEmpty()) return -1;\n\n int[] lps = buildLPS(pattern);\n int n = text.length();\n int m = pattern.length();\n\n int i = 0; // Index in text\n int j = 0; // Index in pattern\n\n while (i < n) {\n if (text.charAt(i) == pattern.charAt(j)) {\n i++;\n j++;\n\n if (j == m) {\n return i - m; // Found at position i - m\n }\n } else {\n if (j != 0) {\n // Use LPS to skip\n j = lps[j - 1];\n } else {\n i++;\n }\n }\n }\n\n return -1;\n }\n\n /**\n * Find all occurrences using KMP.\n */\n public static List searchAll(String text, String pattern) {\n List positions = new ArrayList<>();\n if (pattern.isEmpty()) return positions;\n\n int[] lps = buildLPS(pattern);\n int n = text.length();\n int m = pattern.length();\n\n int i = 0, j = 0;\n\n while (i < n) {\n if (text.charAt(i) == pattern.charAt(j)) {\n i++;\n j++;\n\n if (j == m) {\n positions.add(i - m);\n j = lps[j - 1]; // Continue searching\n }\n } else {\n if (j != 0) {\n j = lps[j - 1];\n } else {\n i++;\n }\n }\n }\n\n return positions;\n }\n}\n```\n\n### LPS Array Example\n\n```text\nLPS ARRAY CONSTRUCTION\n━━━━━━━━━━━━━━━━━━━━━━\n\nPattern: A B A B A C A\nIndex: 0 1 2 3 4 5 6\n\ni=0: lps[0] = 0 (by definition)\ni=1: 'B' vs 'A' - no match, lps[1] = 0\ni=2: 'A' vs 'A' - match! lps[2] = 1\ni=3: 'B' vs 'B' - match! lps[3] = 2\ni=4: 'A' vs 'A' - match! lps[4] = 3\ni=5: 'C' vs 'B' - no match\n len = lps[2] = 1, try 'C' vs 'B' - no match\n len = lps[0] = 0, lps[5] = 0\ni=6: 'A' vs 'A' - match! lps[6] = 1\n\nResult: [0, 0, 1, 2, 3, 0, 1]\n\nInterpretation:\n- lps[4] = 3 means \"ABABA\" has prefix \"ABA\" = suffix \"ABA\"\n- If we match up to index 4 and fail at 5, we can skip back to index 3\n```\n\n---\n\n## 🔬 Deep Dive: Rabin-Karp\n\n### The Hash Approach\n\nInstead of comparing characters, compare hash values. Only do character comparison when hashes match.\n\n```text\nRABIN-KARP CONCEPT\n━━━━━━━━━━━━━━━━━━\n\nText: [A B C D E F G]\nPattern: [C D E]\n\nHash pattern: H(CDE) = 67 + 68 + 69 = 204\n\nSlide window:\n ABC: hash = 65 + 66 + 67 = 198 ≠ 204\n BCD: hash = 66 + 67 + 68 = 201 ≠ 204\n CDE: hash = 67 + 68 + 69 = 204 == 204 → verify characters!\n ...\n\nKey: Compute next hash from previous in O(1) using rolling hash\n```\n\n### Rolling Hash\n\n```java\npublic class RabinKarp {\n private static final long BASE = 256;\n private static final long MOD = 1_000_000_007;\n\n /**\n * Rabin-Karp with rolling hash.\n *\n * Time: O(n + m) average, O(nm) worst case (many hash collisions)\n * Space: O(1)\n */\n public static int search(String text, String pattern) {\n int n = text.length();\n int m = pattern.length();\n if (m > n) return -1;\n if (m == 0) return 0;\n\n // Compute BASE^(m-1) % MOD for removing leading digit\n long basePow = 1;\n for (int i = 0; i < m - 1; i++) {\n basePow = (basePow * BASE) % MOD;\n }\n\n // Compute initial hashes\n long patternHash = 0;\n long textHash = 0;\n\n for (int i = 0; i < m; i++) {\n patternHash = (patternHash * BASE + pattern.charAt(i)) % MOD;\n textHash = (textHash * BASE + text.charAt(i)) % MOD;\n }\n\n // Slide the window\n for (int i = 0; i <= n - m; i++) {\n if (patternHash == textHash) {\n // Verify character by character (hash collision possible)\n if (text.substring(i, i + m).equals(pattern)) {\n return i;\n }\n }\n\n // Compute hash for next window\n if (i < n - m) {\n // Remove leading char, add trailing char\n textHash = (textHash - text.charAt(i) * basePow % MOD + MOD) % MOD;\n textHash = (textHash * BASE + text.charAt(i + m)) % MOD;\n }\n }\n\n return -1;\n }\n\n /**\n * Multiple pattern search - Rabin-Karp shines here!\n * Instead of O(n * p) for p patterns, we get O(n + pm)\n */\n public static Map> searchMultiple(\n String text, List patterns) {\n\n Map> results = new HashMap<>();\n Map> hashToPatterns = new HashMap<>();\n\n // Group patterns by length and precompute hashes\n Map> byLength = new HashMap<>();\n for (String p : patterns) {\n results.put(p, new ArrayList<>());\n byLength.computeIfAbsent(p.length(), k -> new ArrayList<>()).add(p);\n }\n\n int n = text.length();\n\n // Process each pattern length\n for (Map.Entry> entry : byLength.entrySet()) {\n int m = entry.getKey();\n if (m > n) continue;\n\n // Compute pattern hashes\n hashToPatterns.clear();\n for (String p : entry.getValue()) {\n long h = computeHash(p);\n hashToPatterns.computeIfAbsent(h, k -> new ArrayList<>()).add(p);\n }\n\n // Compute BASE^(m-1)\n long basePow = 1;\n for (int i = 0; i < m - 1; i++) {\n basePow = (basePow * BASE) % MOD;\n }\n\n // Rolling hash through text\n long textHash = 0;\n for (int i = 0; i < m; i++) {\n textHash = (textHash * BASE + text.charAt(i)) % MOD;\n }\n\n for (int i = 0; i <= n - m; i++) {\n List candidates = hashToPatterns.get(textHash);\n if (candidates != null) {\n String window = text.substring(i, i + m);\n for (String p : candidates) {\n if (window.equals(p)) {\n results.get(p).add(i);\n }\n }\n }\n\n if (i < n - m) {\n textHash = (textHash - text.charAt(i) * basePow % MOD + MOD) % MOD;\n textHash = (textHash * BASE + text.charAt(i + m)) % MOD;\n }\n }\n }\n\n return results;\n }\n\n private static long computeHash(String s) {\n long hash = 0;\n for (char c : s.toCharArray()) {\n hash = (hash * BASE + c) % MOD;\n }\n return hash;\n }\n}\n```\n\n### When Rabin-Karp Excels\n\n```java\n/**\n * Plagiarism detection: Find common substrings between documents.\n */\npublic class PlagiarismDetector {\n private static final int CHUNK_SIZE = 50; // Compare 50-char chunks\n\n public double similarity(String doc1, String doc2) {\n // Get all k-gram hashes from doc1\n Set doc1Hashes = getChunkHashes(doc1, CHUNK_SIZE);\n\n // Count matches in doc2\n int matches = 0;\n int total = 0;\n\n // Slide through doc2\n long hash = 0;\n long basePow = 1;\n for (int i = 0; i < CHUNK_SIZE - 1; i++) {\n basePow = (basePow * 256) % 1_000_000_007;\n }\n\n for (int i = 0; i < doc2.length(); i++) {\n if (i < CHUNK_SIZE) {\n hash = (hash * 256 + doc2.charAt(i)) % 1_000_000_007;\n } else {\n hash = (hash - doc2.charAt(i - CHUNK_SIZE) * basePow % 1_000_000_007\n + 1_000_000_007) % 1_000_000_007;\n hash = (hash * 256 + doc2.charAt(i)) % 1_000_000_007;\n }\n\n if (i >= CHUNK_SIZE - 1) {\n total++;\n if (doc1Hashes.contains(hash)) {\n matches++;\n }\n }\n }\n\n return total > 0 ? (double) matches / total : 0;\n }\n\n private Set getChunkHashes(String doc, int k) {\n Set hashes = new HashSet<>();\n // Similar rolling hash computation...\n return hashes;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Boyer-Moore\n\n### The Clever Insight\n\nBoyer-Moore compares pattern from right to left, allowing bigger jumps on mismatch.\n\n```text\nBOYER-MOORE RIGHT-TO-LEFT\n━━━━━━━━━━━━━━━━━━━━━━━━━\n\nText: H E R E I S A S I M P L E E X A M P L E\nPattern: E X A M P L E\n\nAttempt 1 (position 0):\nCompare right-to-left: E vs E ✓, L vs ' ' ✗\nMismatch! ' ' doesn't appear in pattern.\nJump entire pattern length!\n\n H E R E I S A S I M P L E E X A M P L E\n E X A M P L E\n\nAttempt 2 (position 7):\nCompare: E vs A ✗\n'A' appears at position 2 in pattern.\nAlign 'A' with 'A' in text.\n\n H E R E I S A S I M P L E E X A M P L E\n E X A M P L E\n\n... continue with smart jumps ...\n```\n\n### Implementation\n\n```java\npublic class BoyerMoore {\n private static final int ALPHABET_SIZE = 256;\n\n /**\n * Boyer-Moore with Bad Character heuristic.\n *\n * Time: O(n/m) best case, O(nm) worst case\n * Space: O(m + σ) where σ = alphabet size\n */\n public static int search(String text, String pattern) {\n int n = text.length();\n int m = pattern.length();\n\n if (m == 0) return 0;\n if (m > n) return -1;\n\n // Bad character table: last occurrence of each character in pattern\n int[] badChar = buildBadCharTable(pattern);\n\n int shift = 0;\n while (shift <= n - m) {\n int j = m - 1;\n\n // Compare from right to left\n while (j >= 0 && pattern.charAt(j) == text.charAt(shift + j)) {\n j--;\n }\n\n if (j < 0) {\n // Pattern found at shift\n return shift;\n }\n\n // Calculate shift using bad character heuristic\n char badCharInText = text.charAt(shift + j);\n int lastOccurrence = badChar[badCharInText];\n\n // Shift to align bad character or move past it\n shift += Math.max(1, j - lastOccurrence);\n }\n\n return -1;\n }\n\n /**\n * Build bad character table.\n * badChar[c] = rightmost position of c in pattern, or -1 if not present.\n */\n private static int[] buildBadCharTable(String pattern) {\n int[] table = new int[ALPHABET_SIZE];\n Arrays.fill(table, -1);\n\n for (int i = 0; i < pattern.length(); i++) {\n table[pattern.charAt(i)] = i;\n }\n\n return table;\n }\n\n /**\n * Boyer-Moore with Good Suffix heuristic (full algorithm).\n * Even better performance but more complex.\n */\n public static int searchWithGoodSuffix(String text, String pattern) {\n int n = text.length();\n int m = pattern.length();\n\n if (m == 0) return 0;\n if (m > n) return -1;\n\n int[] badChar = buildBadCharTable(pattern);\n int[] goodSuffix = buildGoodSuffixTable(pattern);\n\n int shift = 0;\n while (shift <= n - m) {\n int j = m - 1;\n\n while (j >= 0 && pattern.charAt(j) == text.charAt(shift + j)) {\n j--;\n }\n\n if (j < 0) {\n return shift;\n }\n\n // Use maximum of bad char and good suffix shifts\n int badCharShift = j - badChar[text.charAt(shift + j)];\n int goodSuffixShift = goodSuffix[j + 1];\n\n shift += Math.max(badCharShift, goodSuffixShift);\n }\n\n return -1;\n }\n\n /**\n * Build good suffix table.\n */\n private static int[] buildGoodSuffixTable(String pattern) {\n int m = pattern.length();\n int[] goodSuffix = new int[m + 1];\n int[] suffix = new int[m + 1];\n\n // Compute suffix array\n computeSuffix(pattern, suffix);\n\n // Initialize all shifts to m\n Arrays.fill(goodSuffix, m);\n\n // Case 1: Matching suffix appears elsewhere in pattern\n int j = 0;\n for (int i = m - 1; i >= 0; i--) {\n if (suffix[i] == i + 1) {\n while (j < m - 1 - i) {\n if (goodSuffix[j] == m) {\n goodSuffix[j] = m - 1 - i;\n }\n j++;\n }\n }\n }\n\n // Case 2: Part of matching suffix appears at beginning of pattern\n for (int i = 0; i < m - 1; i++) {\n goodSuffix[m - 1 - suffix[i]] = m - 1 - i;\n }\n\n return goodSuffix;\n }\n\n private static void computeSuffix(String pattern, int[] suffix) {\n int m = pattern.length();\n suffix[m - 1] = m;\n\n int g = m - 1;\n int f = 0;\n\n for (int i = m - 2; i >= 0; i--) {\n if (i > g && suffix[i + m - 1 - f] < i - g) {\n suffix[i] = suffix[i + m - 1 - f];\n } else {\n if (i < g) {\n g = i;\n }\n f = i;\n while (g >= 0 && pattern.charAt(g) == pattern.charAt(g + m - 1 - f)) {\n g--;\n }\n suffix[i] = f - g;\n }\n }\n }\n}\n```\n\n### Performance Comparison\n\n```java\n/**\n * Benchmark different string search algorithms.\n */\npublic class StringSearchBenchmark {\n public static void benchmark() {\n String text = generateText(10_000_000); // 10M characters\n String pattern = \"ABCDEFGHIJ\"; // 10-char pattern\n\n // Naive\n long start = System.nanoTime();\n int result1 = naiveSearch(text, pattern);\n long naiveTime = System.nanoTime() - start;\n\n // KMP\n start = System.nanoTime();\n int result2 = KMP.search(text, pattern);\n long kmpTime = System.nanoTime() - start;\n\n // Boyer-Moore\n start = System.nanoTime();\n int result3 = BoyerMoore.search(text, pattern);\n long bmTime = System.nanoTime() - start;\n\n System.out.printf(\"Naive: %d ms%n\", naiveTime / 1_000_000);\n System.out.printf(\"KMP: %d ms%n\", kmpTime / 1_000_000);\n System.out.printf(\"Boyer-Moore: %d ms%n\", bmTime / 1_000_000);\n\n /*\n Typical results (random text, 10-char pattern):\n Naive: 450 ms\n KMP: 45 ms\n Boyer-Moore: 12 ms\n\n Boyer-Moore wins because it skips characters!\n */\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Aho-Corasick\n\n### The Trie + Failure Links\n\nAho-Corasick builds a trie from all patterns, then adds \"failure links\" (like KMP's failure function) to enable efficient searching.\n\n```text\nAHO-CORASICK STRUCTURE\n━━━━━━━━━━━━━━━━━━━━━━\n\nPatterns: \"he\", \"she\", \"his\", \"hers\"\n\nTrie:\n (root)\n / | \\\n h s ...\n / \\ \\\n e i h\n | | |\n r s e\n | |\n s (output: \"she\")\n (output: \"hers\")\n\nFailure links connect back to longest proper suffix that's a prefix:\n- \"she\" → \"he\" (failing at 'e' of \"she\", continue matching \"he\")\n- \"he\" → root\n```\n\n### Implementation\n\n```java\npublic class AhoCorasick {\n private static final int ALPHABET_SIZE = 256;\n\n private final int[][] go; // Trie transitions\n private final int[] fail; // Failure links\n private final List> output; // Pattern indices at each state\n private int stateCount;\n\n /**\n * Build Aho-Corasick automaton from patterns.\n *\n * Time: O(Σ|patterns|) to build\n * Space: O(Σ|patterns| × alphabet_size)\n */\n public AhoCorasick(List patterns) {\n int maxStates = patterns.stream().mapToInt(String::length).sum() + 1;\n\n go = new int[maxStates][ALPHABET_SIZE];\n fail = new int[maxStates];\n output = new ArrayList<>();\n\n for (int i = 0; i < maxStates; i++) {\n Arrays.fill(go[i], -1);\n output.add(new ArrayList<>());\n }\n\n stateCount = 1; // State 0 is root\n\n // Build trie\n for (int i = 0; i < patterns.size(); i++) {\n addPattern(patterns.get(i), i);\n }\n\n // Build failure links using BFS\n buildFailureLinks();\n }\n\n private void addPattern(String pattern, int patternIndex) {\n int state = 0;\n\n for (char c : pattern.toCharArray()) {\n if (go[state][c] == -1) {\n go[state][c] = stateCount++;\n }\n state = go[state][c];\n }\n\n output.get(state).add(patternIndex);\n }\n\n private void buildFailureLinks() {\n Queue queue = new LinkedList<>();\n\n // Initialize depth-1 states\n for (int c = 0; c < ALPHABET_SIZE; c++) {\n if (go[0][c] != -1) {\n fail[go[0][c]] = 0;\n queue.add(go[0][c]);\n } else {\n go[0][c] = 0; // Self-loop at root\n }\n }\n\n // BFS to build failure links\n while (!queue.isEmpty()) {\n int state = queue.poll();\n\n for (int c = 0; c < ALPHABET_SIZE; c++) {\n if (go[state][c] != -1) {\n int next = go[state][c];\n queue.add(next);\n\n // Follow failure links to find longest proper suffix\n int fallback = fail[state];\n while (go[fallback][c] == -1) {\n fallback = fail[fallback];\n }\n fail[next] = go[fallback][c];\n\n // Merge outputs\n output.get(next).addAll(output.get(fail[next]));\n }\n }\n }\n }\n\n /**\n * Search for all pattern occurrences in text.\n *\n * Time: O(n + z) where z = number of matches\n */\n public List search(String text) {\n List matches = new ArrayList<>();\n int state = 0;\n\n for (int i = 0; i < text.length(); i++) {\n char c = text.charAt(i);\n\n // Follow failure links until we find a valid transition\n while (go[state][c] == -1) {\n state = fail[state];\n }\n state = go[state][c];\n\n // Record all patterns ending at this position\n for (int patternIdx : output.get(state)) {\n matches.add(new Match(patternIdx, i));\n }\n }\n\n return matches;\n }\n\n public record Match(int patternIndex, int endPosition) {}\n}\n```\n\n### Usage Example\n\n```java\npublic class AhoCorasickDemo {\n public static void main(String[] args) {\n List patterns = Arrays.asList(\"he\", \"she\", \"his\", \"hers\");\n AhoCorasick ac = new AhoCorasick(patterns);\n\n String text = \"ushers\";\n\n List matches = ac.search(text);\n\n // Output:\n // Pattern 0 (\"he\") at position 2-3: \"usHErs\"\n // Pattern 1 (\"she\") at position 1-3: \"uSHErs\"\n // Pattern 3 (\"hers\") at position 2-5: \"usHERS\"\n\n for (AhoCorasick.Match m : matches) {\n System.out.printf(\"Pattern '%s' ends at position %d%n\",\n patterns.get(m.patternIndex()), m.endPosition());\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Java's String.indexOf()\n\n### The Implementation\n\nJava's `String.indexOf()` uses a simple but effective approach:\n\n```java\n/**\n * Simplified version of Java's String.indexOf() logic.\n */\npublic class JavaStringIndexOf {\n /**\n * Java's approach: Naive with early termination optimization.\n *\n * Why not KMP or Boyer-Moore?\n * 1. Preprocessing overhead - not worth it for short patterns\n * 2. Real-world strings are mostly short\n * 3. Cache-friendly sequential access\n * 4. JIT can optimize the tight loop\n */\n public static int indexOf(String source, String target) {\n int sourceLength = source.length();\n int targetLength = target.length();\n\n if (targetLength == 0) return 0;\n if (targetLength > sourceLength) return -1;\n\n char first = target.charAt(0);\n int max = sourceLength - targetLength;\n\n for (int i = 0; i <= max; i++) {\n // Look for first character\n if (source.charAt(i) != first) {\n while (++i <= max && source.charAt(i) != first);\n }\n\n // Found first character, now verify rest\n if (i <= max) {\n int j = i + 1;\n int end = j + targetLength - 1;\n for (int k = 1; j < end && source.charAt(j) == target.charAt(k); j++, k++);\n\n if (j == end) {\n return i; // Found\n }\n }\n }\n\n return -1;\n }\n}\n```\n\n### When to Use Standard Library vs Custom\n\n| Scenario | Recommendation |\n|----------|----------------|\n| Short pattern, short text | `String.indexOf()` |\n| Short pattern, long text | `String.indexOf()` (JIT optimizes well) |\n| Long pattern, long text | Boyer-Moore |\n| Multiple searches, same pattern | Precompile KMP/BM |\n| Multiple patterns | Aho-Corasick |\n| Streaming text | KMP (no backtracking) |\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Wrong LPS Computation\n\n```java\n// ❌ Incorrect: Comparing with i instead of len\nwhile (i < m) {\n if (pattern.charAt(i) == pattern.charAt(i - 1)) { // Wrong!\n // ...\n }\n}\n\n// ✅ Correct: Compare position i with position len\nwhile (i < m) {\n if (pattern.charAt(i) == pattern.charAt(len)) {\n len++;\n lps[i] = len;\n i++;\n } else {\n // ...\n }\n}\n```\n\n### Mistake 2: Integer Overflow in Rabin-Karp\n\n```java\n// ❌ Overflow without modular arithmetic\nlong hash = 0;\nfor (char c : pattern.toCharArray()) {\n hash = hash * 256 + c; // Overflows for long patterns!\n}\n\n// ✅ Use modular arithmetic\nfor (char c : pattern.toCharArray()) {\n hash = (hash * 256 + c) % MOD;\n}\n```\n\n### Mistake 3: Negative Hash in Rolling Window\n\n```java\n// ❌ Can produce negative hash\ntextHash = (textHash - text.charAt(i) * basePow) * BASE + text.charAt(i + m);\ntextHash %= MOD; // Still negative if subtraction went negative!\n\n// ✅ Add MOD before taking modulo\ntextHash = (textHash - text.charAt(i) * basePow % MOD + MOD) % MOD;\ntextHash = (textHash * BASE + text.charAt(i + m)) % MOD;\n```\n\n### Mistake 4: Boyer-Moore Bad Character Shift\n\n```java\n// ❌ Can cause backward shift\nshift += j - badChar[badCharInText]; // If badChar > j, this goes backward!\n\n// ✅ Ensure forward progress\nshift += Math.max(1, j - badChar[badCharInText]);\n```\n\n---\n\n## 🐛 Debug This: The Broken String Search\n\nThese implementations have bugs. Find and fix them:\n\n```java\npublic class BrokenStringSearch {\n\n // Bug 1: KMP failure function\n public int[] buildLPS(String pattern) {\n int m = pattern.length();\n int[] lps = new int[m];\n int len = 0;\n int i = 0; // Bug\n\n while (i < m) {\n if (pattern.charAt(i) == pattern.charAt(len)) {\n lps[i] = len; // Bug\n len++;\n i++;\n } else {\n if (len != 0) {\n len = lps[len]; // Bug\n } else {\n lps[i] = 0;\n i++;\n }\n }\n }\n return lps;\n }\n\n // Bug 2: Rabin-Karp\n public int rabinKarp(String text, String pattern) {\n long patternHash = 0, textHash = 0;\n int m = pattern.length();\n long basePow = (long) Math.pow(256, m - 1); // Bug\n\n for (int i = 0; i < m; i++) {\n patternHash = patternHash * 256 + pattern.charAt(i);\n textHash = textHash * 256 + text.charAt(i);\n }\n\n for (int i = 0; i < text.length() - m; i++) { // Bug\n if (patternHash == textHash) {\n return i; // Bug: no verification\n }\n textHash = (textHash - text.charAt(i) * basePow) * 256\n + text.charAt(i + m);\n }\n return -1;\n }\n}\n```\n\n

💡 Hint

\n\nLook for:\n1. LPS initialization and indexing\n2. Math.pow precision issues\n3. Loop bounds and modular arithmetic\n4. Hash collision handling\n\n

\n\n

✅ Solution

\n\n```java\npublic class FixedStringSearch {\n\n // ✅ Fix 1: KMP failure function\n public int[] buildLPS(String pattern) {\n int m = pattern.length();\n int[] lps = new int[m];\n lps[0] = 0; // ✅ Initialize first element\n int len = 0;\n int i = 1; // ✅ Start from 1, not 0\n\n while (i < m) {\n if (pattern.charAt(i) == pattern.charAt(len)) {\n len++;\n lps[i] = len; // ✅ Assign len after increment\n i++;\n } else {\n if (len != 0) {\n len = lps[len - 1]; // ✅ Use len - 1, not len\n } else {\n lps[i] = 0;\n i++;\n }\n }\n }\n return lps;\n }\n\n // ✅ Fix 2: Rabin-Karp\n private static final long MOD = 1_000_000_007;\n\n public int rabinKarp(String text, String pattern) {\n if (pattern.length() > text.length()) return -1;\n\n long patternHash = 0, textHash = 0;\n int m = pattern.length();\n\n // ✅ Compute basePow with modular arithmetic\n long basePow = 1;\n for (int i = 0; i < m - 1; i++) {\n basePow = (basePow * 256) % MOD;\n }\n\n for (int i = 0; i < m; i++) {\n patternHash = (patternHash * 256 + pattern.charAt(i)) % MOD;\n textHash = (textHash * 256 + text.charAt(i)) % MOD;\n }\n\n // ✅ Fix loop bounds: <= not <\n for (int i = 0; i <= text.length() - m; i++) {\n if (patternHash == textHash) {\n // ✅ Verify to handle hash collisions\n if (text.substring(i, i + m).equals(pattern)) {\n return i;\n }\n }\n\n // ✅ Only update if not at the end\n if (i < text.length() - m) {\n // ✅ Handle negative modulo\n textHash = (textHash - text.charAt(i) * basePow % MOD + MOD) % MOD;\n textHash = (textHash * 256 + text.charAt(i + m)) % MOD;\n }\n }\n return -1;\n }\n}\n```\n\n**Bugs explained:**\n\n1. **LPS function**:\n - Starting i at 0 would try to compare `pattern.charAt(0)` with itself\n - `lps[i] = len` before incrementing would be off-by-one\n - `lps[len]` should be `lps[len-1]` (previous prefix)\n\n2. **Rabin-Karp**:\n - `Math.pow` returns double, loses precision for large exponents\n - Loop `< text.length() - m` misses last position\n - No verification allows false positives from hash collisions\n - No modular arithmetic causes overflow and negative remainders\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Count Pattern Occurrences ⭐\n\nImplement a function to count all occurrences of a pattern in text.\n\n```java\npublic class PatternCounter {\n /**\n * Count occurrences of pattern in text.\n * Handle overlapping matches (e.g., \"aa\" in \"aaa\" = 2)\n */\n public int count(String text, String pattern) {\n // Your implementation using KMP\n }\n}\n```\n\n---\n\n### Exercise 2: First Unique Substring ⭐⭐\n\nFind the shortest substring of text that doesn't appear elsewhere in text.\n\n```java\npublic class FirstUniqueSubstring {\n /**\n * Find shortest substring that appears exactly once.\n * Return the substring, or empty string if all substrings repeat.\n */\n public String findFirstUnique(String text) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nUse Rabin-Karp with rolling hash to check each length starting from 1.\n\n

\n\n---\n\n### Exercise 3: Wildcard Pattern Matching ⭐⭐⭐\n\nExtend string search to support wildcards.\n\n```java\npublic class WildcardSearch {\n /**\n * Search with '?' matching any single character\n * and '*' matching any sequence (including empty).\n *\n * Example: pattern \"a*b?c\" matches \"aXXXbYc\"\n */\n public boolean matches(String text, String pattern) {\n // Your implementation\n }\n\n public List findAll(String text, String pattern) {\n // Your implementation\n }\n}\n```\n\n---\n\n### Exercise 4: Longest Repeated Substring ⭐⭐⭐\n\nFind the longest substring that appears at least twice.\n\n```java\npublic class LongestRepeatedSubstring {\n /**\n * Find longest substring appearing 2+ times.\n * Example: \"banana\" → \"ana\" (positions 1 and 3)\n *\n * Time: O(n² log n) using binary search + Rabin-Karp\n * Better: O(n) using suffix array (advanced topic)\n */\n public String find(String text) {\n // Your implementation using binary search on length + Rabin-Karp\n }\n}\n```\n\n---\n\n### Exercise 5: DNA Sequence Alignment ⭐⭐⭐⭐\n\nFind all approximate matches allowing k mismatches.\n\n```java\npublic class ApproximateSearch {\n /**\n * Find all positions where pattern matches with at most k mismatches.\n * Example: pattern=\"ABC\", text=\"AXBXC\", k=2 → matches at position 0\n */\n public List search(String text, String pattern, int k) {\n // Your implementation\n }\n}\n```\n\n

💡 Hint

\n\nSplit pattern into k+1 segments. At least one segment must match exactly (pigeonhole principle). Use exact search for segments, then verify full pattern.\n\n

\n\n---\n\n## 🎤 Interview Questions\n\n### Question 1: Compare KMP and Boyer-Moore\n\n**Answer:**\n\n| Aspect | KMP | Boyer-Moore |\n|--------|-----|-------------|\n| Comparison direction | Left to right | Right to left |\n| Best case | O(n) | O(n/m) - sublinear! |\n| Worst case | O(n) | O(nm) |\n| Preprocessing | O(m) | O(m + σ) |\n| Space | O(m) | O(m + σ) |\n| Streaming | Yes (no backtrack) | No (needs random access) |\n\n**When to use KMP:**\n- Streaming text (can't go back)\n- Guaranteed O(n) important\n- Small patterns\n\n**When to use Boyer-Moore:**\n- Large alphabet (natural language)\n- Long patterns\n- Can afford preprocessing\n\n**In practice:** Boyer-Moore is faster for most real-world cases because it skips characters.\n\n---\n\n### Question 2: How would you search for multiple patterns efficiently?\n\n**Answer:**\n\nThree approaches:\n\n1. **Run single-pattern search for each** - O(n × p) where p = number of patterns. Simple but slow.\n\n2. **Rabin-Karp with multiple hashes** - O(n × max_pattern_length). Good when patterns have similar lengths.\n\n3. **Aho-Corasick** - O(n + z) where z = total matches. Best for many patterns.\n\n```java\n// Approach comparison for searching 100 patterns in 1MB text:\n// 1. KMP × 100: ~100 × 1M = 100M operations\n// 2. Rabin-Karp: ~1M × (hash lookups) ≈ 1M operations\n// 3. Aho-Corasick: ~1M operations (single pass!)\n```\n\n**Recommendation:** For < 10 patterns, run individually. For 10+ patterns, build Aho-Corasick automaton.\n\n---\n\n### Question 3: Why does String.indexOf() use naive search?\n\n**Answer:**\n\nJava's decision makes sense for several reasons:\n\n1. **Preprocessing overhead**: KMP needs O(m) preprocessing. For short patterns (most common case), this exceeds the search time savings.\n\n2. **JIT optimization**: The tight loop in naive search is highly optimizable by the JIT compiler - can vectorize comparisons.\n\n3. **Cache efficiency**: Sequential memory access in naive search is cache-friendly.\n\n4. **Average case**: Real-world strings aren't adversarial. The O(nm) worst case rarely occurs.\n\n5. **Code complexity**: Simple code is easier to maintain and less bug-prone.\n\n**When you should use KMP/BM:**\n- Searching same pattern multiple times\n- Known adversarial patterns (regex engines)\n- Very long texts (> 1MB)\n- Streaming data\n\n---\n\n### Question 4: Explain rolling hash in Rabin-Karp\n\n**Answer:**\n\nRolling hash computes the next window's hash from the current in O(1):\n\n```text\nWindow \"ABC\" → \"BCD\"\n\nHash(ABC) = A×256² + B×256 + C\nHash(BCD) = B×256² + C×256 + D\n\nRelationship:\nHash(BCD) = (Hash(ABC) - A×256²) × 256 + D\n\nGeneral formula:\nnew_hash = (old_hash - first_char × base^(m-1)) × base + new_char\n```\n\n**Key considerations:**\n\n1. **Modular arithmetic**: Use prime modulus to prevent overflow\n2. **Negative handling**: `(hash - x % MOD + MOD) % MOD`\n3. **Collision handling**: Always verify actual characters when hashes match\n4. **Base selection**: Use 256 for ASCII, larger for Unicode\n\n---\n\n### Question 5: How does Aho-Corasick differ from running KMP multiple times?\n\n**Answer:**\n\n**KMP × n patterns:**\n- Time: O(text_length × num_patterns)\n- Space: O(max_pattern_length)\n- Each pattern searched independently\n\n**Aho-Corasick:**\n- Time: O(text_length + total_pattern_length + num_matches)\n- Space: O(total_pattern_length × alphabet_size)\n- All patterns searched simultaneously\n\n**How Aho-Corasick works:**\n\n1. Build trie from all patterns\n2. Add \"failure links\" (like KMP's LPS) between nodes\n3. Single pass through text follows trie transitions\n4. Failure links handle partial matches\n\n**Example benefit:**\nSearching for \"he\", \"she\", \"her\" in text:\n- When matching \"she\", we automatically also match \"he\"\n- Failure link from \"she\" points to \"he\" node\n- No redundant comparisons\n\n---\n\n## 📋 Quick Reference\n\n### Algorithm Selection\n\n| Criteria | Best Algorithm |\n|----------|----------------|\n| Single pattern, general | KMP |\n| Single pattern, large alphabet | Boyer-Moore |\n| Single pattern, streaming | KMP |\n| Multiple patterns | Aho-Corasick |\n| Approximate matching | Rabin-Karp variant |\n| Short text, any pattern | Naive (String.indexOf) |\n\n### Complexity Comparison\n\n| Algorithm | Preprocessing | Search | Space |\n|-----------|---------------|--------|-------|\n| Naive | O(1) | O(nm) | O(1) |\n| KMP | O(m) | O(n) | O(m) |\n| Rabin-Karp | O(m) | O(n) avg | O(1) |\n| Boyer-Moore | O(m + σ) | O(n/m) to O(nm) | O(m + σ) |\n| Aho-Corasick | O(Σm) | O(n + z) | O(Σm × σ) |\n\n### Java Built-in Methods\n\n```java\n// Basic search\nint idx = text.indexOf(pattern); // First occurrence\nint idx = text.indexOf(pattern, fromIndex); // From position\nint idx = text.lastIndexOf(pattern); // Last occurrence\n\n// Contains check\nboolean found = text.contains(pattern);\n\n// Regex (more powerful but slower)\nPattern p = Pattern.compile(regex);\nMatcher m = p.matcher(text);\nwhile (m.find()) {\n // Process match\n}\n\n// Split (uses pattern matching internally)\nString[] parts = text.split(pattern);\n```\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| Day 1 | Read article, understand KMP LPS construction | 60 min |\n| Day 3 | Implement KMP from scratch | 30 min |\n| Day 7 | Implement Rabin-Karp with rolling hash | 30 min |\n| Day 14 | Build simple Aho-Corasick for 3 patterns | 45 min |\n| Day 30 | Solve string search problems (LeetCode) | 30 min |\n\n---\n\n## 🔗 What's Next?\n\n**Part 11: Graph Representation & Traversal** covers:\n- Adjacency list vs matrix tradeoffs\n- Graph implementation in Java\n- DFS: recursive vs iterative\n- BFS: shortest path in unweighted graphs\n- Topological sort\n- Cycle detection\n\n**Key insight preview**: Graphs are everywhere - social networks, maps, dependencies, state machines. Mastering graph traversal unlocks an enormous class of problems.\n\n---\n\n*This article is part of the Algorithms Compendium series. For the complete learning path, see Part 0: How to Use This Series.*\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.145830Z","createdAt","2026-06-10T07:19:25.146837Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",27,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder","author",{"_31":55,"_102":57,"_103":104,"_105":106,"_107":-5,"_108":-5,"_109":-5,"_110":-5,"_111":-5},"category",{"_31":98,"_72":59,"_35":99,"_75":100,"_101":-5},"tags",[78,79,80,81,82],"series",{"_31":62,"_72":73,"_35":74,"_75":76,"_77":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":95,"_72":96,"_35":97},{"_31":92,"_72":93,"_35":94},{"_31":89,"_72":90,"_35":91},{"_31":86,"_72":87,"_35":88},{"_31":83,"_72":84,"_35":85},157,"Rabin-karp","rabin-karp",107,"Pattern Matching","pattern-matching",156,"Kmp","kmp",158,"Boyer-moore","boyer-moore",159,"Aho-corasick","aho-corasick",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]