String Algorithms

Also Known As

TL;DR

Explanation

Naive string search: O(n×m). KMP (Knuth-Morris-Pratt): O(n+m) — preprocessing the pattern avoids re-scanning matched characters. Boyer-Moore: O(n/m) in best case — scans right to left, skips large portions. Rabin-Karp: O(n+m) average — uses rolling hash, natural for multi-pattern search and plagiarism detection. Levenshtein distance: minimum edit distance between two strings — used in fuzzy search and spell checkers. In PHP: strpos() uses optimised native search, similar_text() and levenshtein() for fuzzy matching.

Common Misconception

Why It Matters

Common Mistakes

• levenshtein() in a loop against all database rows — O(n×m×rows); use a search engine with fuzzy indexing.
• Reimplementing strpos() in PHP — native function is C-optimised; PHP implementation will be 100× slower.
• Not using mb_strpos() for Unicode strings — strpos() operates on bytes and returns wrong positions for multibyte chars.
• similar_text() for ranking — it is O(max(n,m)³); not suitable for large-scale text comparison.

Code Examples

// Levenshtein against all rows — O(n × string_length × row_count):
$query = 'phyton'; // Misspelled
$allTerms = $db->query('SELECT slug, term FROM glossary')->fetchAll();
$matches = [];
foreach ($allTerms as $term) {
    if (levenshtein($query, strtolower($term['term'])) <= 2) {
        $matches[] = $term; // O(m) per row, all rows scanned
    }
}

// Use search engine fuzzy query instead:
$results = $elasticsearch->search([
    'query' => ['match' => ['term' => ['query' => $query, 'fuzziness' => 'AUTO']]]
]);
// O(log n) with indexed fuzzy matching

// Or PostgreSQL pg_trgm:
// SELECT * FROM glossary WHERE term % 'phyton' ORDER BY term <-> 'phyton' LIMIT 10;
// Index: CREATE INDEX ON glossary USING gin(term gin_trgm_ops);

References

• ↗ https://en.wikipedia.org/wiki/String-searching_algorithm

Tags

Related Terms