String problems are about finding a pattern inside a text without re-comparing characters you have already looked at. Naive matching restarts from scratch after every mismatch; Rabin–Karp compares hashes first; KMP precomputes exactly how far the pattern can safely slide. Around them sit the classic sliding-window and counting problems: anagram search, longest distinct substring and the lexicographic rank of a string.

The landscape of pattern-searching algorithms

Preprocessing	Algorithm	Time	Notes
none	naive	`O((n − m + 1) · m)`	simple; the bound is tight for `txt = aaaa…`, `pat = aaab`
none	naive, pattern characters distinct	`O(n)`	after a mismatch at `j`, slide by `j`
pattern	Rabin–Karp	`O((n − m + 1) · m)` worst, `O(n + m)` expected	compares a rolling hash first; great for many patterns of the same length
pattern	KMP (Knuth–Morris–Pratt)	`O(n + m)` guaranteed	LPS array tells how far to fall back; never re-reads a text character
text	suffix tree / suffix array	`O(m)` per query after `O(n)` build	when the same text is searched for many patterns

Naive pattern searching

Library search already does this: Python's str.find(pat, start) repeated from pos + 1 finds every (possibly overlapping) occurrence.

Python — using str.find

def find_all(txt, pat):
    pos = txt.find(pat)
    while pos >= 0:
        print(pos, end=" ")
        pos = txt.find(pat, pos + 1)      # start just after the last hit → overlaps are found too
    print()

find_all("GEEKSFORGEEKS", "EKS")
find_all("AAAA", "AAA")

Output

2 10
0 1

Python

def naive_search(txt, pat):
    n, m = len(txt), len(pat)
    res = []
    for i in range(n - m + 1):              # every candidate start
        j = 0
        while j < m and txt[i + j] == pat[j]:
            j += 1
        if j == m:                          # all m characters matched
            res.append(i)
    return res

for txt, pat in [("GEEKSFORGEEKS", "EKS"), ("AAAA", "AAA"), ("geeks for geeks", "geeks")]:
    print(pat, "in", txt, "→", " ".join(map(str, naive_search(txt, pat))))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> naiveSearch(const string& txt, const string& pat) {
    int n = txt.size(), m = pat.size();
    vector<int> res;
    for (int i = 0; i + m <= n; i++) {           // every candidate start
        int j = 0;
        while (j < m && txt[i + j] == pat[j]) j++;
        if (j == m) res.push_back(i);            // all m characters matched
    }
    return res;
}

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? " " : "") + to_string(v[i]);
    return s;
}

int main() {
    vector<pair<string, string>> tests = {{"GEEKSFORGEEKS", "EKS"}, {"AAAA", "AAA"}, {"geeks for geeks", "geeks"}};
    for (auto& [txt, pat] : tests)
        cout << pat << " in " << txt << " → " << join(naiveSearch(txt, pat)) << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> naiveSearch(String txt, String pat) {
        int n = txt.length(), m = pat.length();
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i + m <= n; i++) {                // every candidate start
            int j = 0;
            while (j < m && txt.charAt(i + j) == pat.charAt(j)) j++;
            if (j == m) res.add(i);                       // all m characters matched
        }
        return res;
    }

    static String join(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        return sb.toString();
    }

    public static void main(String[] args) {
        String[][] tests = {{"GEEKSFORGEEKS", "EKS"}, {"AAAA", "AAA"}, {"geeks for geeks", "geeks"}};
        for (String[] t : tests)
            System.out.println(t[1] + " in " + t[0] + " → " + join(naiveSearch(t[0], t[1])));
    }
}

JavaScript

function naiveSearch(txt, pat) {
    const n = txt.length, m = pat.length;
    const res = [];
    for (let i = 0; i + m <= n; i++) {               // every candidate start
        let j = 0;
        while (j < m && txt[i + j] === pat[j]) j++;
        if (j === m) res.push(i);                    // all m characters matched
    }
    return res;
}

for (const [txt, pat] of [["GEEKSFORGEEKS", "EKS"], ["AAAA", "AAA"], ["geeks for geeks", "geeks"]])
    console.log(pat, "in", txt, "→", naiveSearch(txt, pat).join(" "));

Output

EKS in GEEKSFORGEEKS → 2 10
AAA in AAAA → 0 1
geeks in geeks for geeks → 0 10

Time O((n − m + 1) · m) · Space O(1)

Improved naive when the pattern's characters are distinct

Text characters are never re-scanned from the middle of a partial match

txt :  A B C A B C D A B C D
pat :  A B C D                 mismatch at j = 3 (A ≠ D)
             A B C D           slide by 3 → match at i = 3
                     A B C D   slide by m = 4 → match at i = 7

Python

def distinct_search(txt, pat):
    n, m = len(txt), len(pat)
    res = []
    i = 0
    while i <= n - m:
        j = 0
        while j < m and txt[i + j] == pat[j]:
            j += 1
        if j == m:
            res.append(i)
        i += max(1, j)            # slide by j (by 1 when the very first character failed)
    return res

print(" ".join(map(str, distinct_search("ABCABCDABCD", "ABCD"))))
print(" ".join(map(str, distinct_search("AAAB", "AB"))))

C++

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> distinctSearch(const string& txt, const string& pat) {
    int n = txt.size(), m = pat.size();
    vector<int> res;
    int i = 0;
    while (i <= n - m) {
        int j = 0;
        while (j < m && txt[i + j] == pat[j]) j++;
        if (j == m) res.push_back(i);
        i += max(1, j);                // slide by j (by 1 when the very first character failed)
    }
    return res;
}

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? " " : "") + to_string(v[i]);
    return s;
}

int main() {
    cout << join(distinctSearch("ABCABCDABCD", "ABCD")) << "\n";
    cout << join(distinctSearch("AAAB", "AB")) << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<Integer> distinctSearch(String txt, String pat) {
        int n = txt.length(), m = pat.length();
        List<Integer> res = new ArrayList<>();
        int i = 0;
        while (i <= n - m) {
            int j = 0;
            while (j < m && txt.charAt(i + j) == pat.charAt(j)) j++;
            if (j == m) res.add(i);
            i += Math.max(1, j);       // slide by j (by 1 when the very first character failed)
        }
        return res;
    }

    static String join(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(join(distinctSearch("ABCABCDABCD", "ABCD")));
        System.out.println(join(distinctSearch("AAAB", "AB")));
    }
}

JavaScript

function distinctSearch(txt, pat) {
    const n = txt.length, m = pat.length;
    const res = [];
    let i = 0;
    while (i <= n - m) {
        let j = 0;
        while (j < m && txt[i + j] === pat[j]) j++;
        if (j === m) res.push(i);
        i += Math.max(1, j);           // slide by j (by 1 when the very first character failed)
    }
    return res;
}

console.log(distinctSearch("ABCABCDABCD", "ABCD").join(" "));
console.log(distinctSearch("AAAB", "AB").join(" "));

Output

3 7
2

Time O(n) · Space O(1)

Rabin–Karp with a rolling hash

Like the naive algorithm, slide the pattern over every start — but compare a hash of the pattern with a hash of the current window first, and only compare characters when the hashes agree. The trick is computing the next window's hash from the previous one in O(1) — a rolling hash.

A first attempt: the sum of character codes
t(i+1) = t(i) + txt[i+m] − txt[i] — O(1) per shift, but every anagram of the pattern (abc, bca, cab) has the same hash, so spurious hits are common.
A better hash: treat the window as a base-d number
h(s) = s[0]·d^(m−1) + s[1]·d^(m−2) + … + s[m−1]·d^0. With d = 5 and a = 1, b = 2, c = 3, d = 4: h("abc") = 1·25 + 2·5 + 3 = 38, h("dab") = 4·25 + 1·5 + 2 = 107. Position now matters.
Roll it
Remove the leading digit, shift left, append the new digit: t(i+1) = d · (t(i) − txt[i] · d^(m−1)) + txt[i+m]. Three multiplications and two additions — O(1) whatever m is.
Keep numbers small
Take everything modulo a prime q (d = 256 for bytes, q = 101 in the examples). Equal hashes are then only probably equal strings — the character check settles it.

t(i+1) = ( d · ( t(i) − txt[i] · d^(m−1) ) + txt[i+m] ) mod q

Python

d, q = 256, 101                              # alphabet size, prime modulus

def rabin_karp(txt, pat):
    n, m = len(txt), len(pat)
    h = 1                                    # h = d^(m-1) mod q
    for _ in range(m - 1):
        h = (h * d) % q
    p = t = 0
    for i in range(m):                       # hash of the pattern and of the first window
        p = (p * d + ord(pat[i])) % q
        t = (t * d + ord(txt[i])) % q
    hits, spurious = [], []
    for i in range(n - m + 1):
        if p == t:                           # hashes agree → verify character by character
            if txt[i:i + m] == pat:
                hits.append(i)
            else:
                spurious.append(i)
        if i < n - m:                        # roll: drop txt[i], append txt[i+m]
            t = (d * (t - ord(txt[i]) * h) + ord(txt[i + m])) % q
            if t < 0:
                t += q                       # (Python's % is never negative; kept for symmetry)
    return hits, spurious

for txt, pat in [("geeks for geeks", "geeks"), ("GEEKSFORGEEKS", "EKS"), ("aaaaab", "aaaa")]:
    hits, spurious = rabin_karp(txt, pat)
    line = pat + " in " + txt + " → " + " ".join(map(str, hits))
    if spurious:
        line += " (spurious hits at " + " ".join(map(str, spurious)) + ")"
    print(line)

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int d = 256, q = 101;                  // alphabet size, prime modulus

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? " " : "") + to_string(v[i]);
    return s;
}

void rabinKarp(const string& txt, const string& pat) {
    int n = txt.size(), m = pat.size();
    int h = 1;                                // h = d^(m-1) mod q
    for (int i = 0; i < m - 1; i++) h = (h * d) % q;
    int p = 0, t = 0;
    for (int i = 0; i < m; i++) {             // hash of the pattern and of the first window
        p = (p * d + pat[i]) % q;
        t = (t * d + txt[i]) % q;
    }
    vector<int> hits, spurious;
    for (int i = 0; i <= n - m; i++) {
        if (p == t) {                         // hashes agree → verify character by character
            if (txt.compare(i, m, pat) == 0) hits.push_back(i);
            else spurious.push_back(i);
        }
        if (i < n - m) {                      // roll: drop txt[i], append txt[i+m]
            t = (d * (t - txt[i] * h) + txt[i + m]) % q;
            if (t < 0) t += q;                // C++ % can be negative
        }
    }
    cout << pat << " in " << txt << " → " << join(hits);
    if (!spurious.empty()) cout << " (spurious hits at " << join(spurious) << ")";
    cout << "\n";
}

int main() {
    rabinKarp("geeks for geeks", "geeks");
    rabinKarp("GEEKSFORGEEKS", "EKS");
    rabinKarp("aaaaab", "aaaa");
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final int d = 256, q = 101;        // alphabet size, prime modulus

    static String join(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        return sb.toString();
    }

    static void rabinKarp(String txt, String pat) {
        int n = txt.length(), m = pat.length();
        int h = 1;                            // h = d^(m-1) mod q
        for (int i = 0; i < m - 1; i++) h = (h * d) % q;
        int p = 0, t = 0;
        for (int i = 0; i < m; i++) {         // hash of the pattern and of the first window
            p = (p * d + pat.charAt(i)) % q;
            t = (t * d + txt.charAt(i)) % q;
        }
        List<Integer> hits = new ArrayList<>(), spurious = new ArrayList<>();
        for (int i = 0; i <= n - m; i++) {
            if (p == t) {                     // hashes agree → verify character by character
                if (txt.startsWith(pat, i)) hits.add(i);
                else spurious.add(i);
            }
            if (i < n - m) {                  // roll: drop txt[i], append txt[i+m]
                t = (d * (t - txt.charAt(i) * h) + txt.charAt(i + m)) % q;
                if (t < 0) t += q;            // Java % can be negative
            }
        }
        String line = pat + " in " + txt + " → " + join(hits);
        if (!spurious.isEmpty()) line += " (spurious hits at " + join(spurious) + ")";
        System.out.println(line);
    }

    public static void main(String[] args) {
        rabinKarp("geeks for geeks", "geeks");
        rabinKarp("GEEKSFORGEEKS", "EKS");
        rabinKarp("aaaaab", "aaaa");
    }
}

JavaScript

const d = 256, q = 101;                        // alphabet size, prime modulus

function rabinKarp(txt, pat) {
    const n = txt.length, m = pat.length;
    let h = 1;                                 // h = d^(m-1) mod q
    for (let i = 0; i < m - 1; i++) h = (h * d) % q;
    let p = 0, t = 0;
    for (let i = 0; i < m; i++) {              // hash of the pattern and of the first window
        p = (p * d + pat.charCodeAt(i)) % q;
        t = (t * d + txt.charCodeAt(i)) % q;
    }
    const hits = [], spurious = [];
    for (let i = 0; i <= n - m; i++) {
        if (p === t) {                         // hashes agree → verify character by character
            if (txt.startsWith(pat, i)) hits.push(i);
            else spurious.push(i);
        }
        if (i < n - m) {                       // roll: drop txt[i], append txt[i+m]
            t = (d * (t - txt.charCodeAt(i) * h) + txt.charCodeAt(i + m)) % q;
            if (t < 0) t += q;                 // JavaScript % can be negative
        }
    }
    let line = pat + " in " + txt + " → " + hits.join(" ");
    if (spurious.length) line += " (spurious hits at " + spurious.join(" ") + ")";
    console.log(line);
}

rabinKarp("geeks for geeks", "geeks");
rabinKarp("GEEKSFORGEEKS", "EKS");
rabinKarp("aaaaab", "aaaa");

Output

geeks in geeks for geeks → 0 10
EKS in GEEKSFORGEEKS → 2 10 (spurious hits at 5)
aaaa in aaaaab → 0 1

Time O(n + m) expected, O(n · m) worst · Space O(1)

KMP: the LPS array (longest proper prefix which is also a suffix)

A proper prefix of a string is a prefix that is not the whole string; likewise for suffixes. For "abc": proper prefixes "", "a", "ab"; proper suffixes "", "c", "bc". lps[i] is the length of the longest proper prefix of pat[0..i] that is also a suffix of pat[0..i].

lps for "ababc" = [0, 0, 1, 2, 0]

pat[0..i]    longest proper prefix that is also a suffix    lps[i]
a            ""                                                0
ab           ""                                                0
aba          "a"                                               1
abab         "ab"                                              2
ababc        ""                                                0

Computing each entry by brute force — try every length from i down to 1 and compare — is simple but cubic:

Python — naive

def longest_proper_prefix_suffix(s):
    n = len(s)
    for length in range(n - 1, 0, -1):             # longest first
        if s[:length] == s[n - length:]:
            return length
    return 0

def lps_naive(pat):
    return [longest_proper_prefix_suffix(pat[:i + 1]) for i in range(len(pat))]

print(lps_naive("ababc"))
print(lps_naive("abacabad"))

Output

[0, 0, 1, 2, 0]
[0, 0, 1, 0, 1, 2, 3, 0]

Time O(n³) · Space O(n)

Falling back through shorter prefix-suffix candidates instead of rescanning

pat = a b a c a b a d        lps so far = 0 0 1 0 1 2 3 ?       (i = 7, len = lps[6] = 3)

pat[3] = 'c' ≠ pat[7] = 'd'   →  len = lps[2] = 1
pat[1] = 'b' ≠ 'd'            →  len = lps[0] = 0
pat[0] = 'a' ≠ 'd', len == 0  →  lps[7] = 0

Python

def compute_lps(pat):
    m = len(pat)
    lps = [0] * m
    length = 0                         # length of the previous longest prefix-suffix
    i = 1
    while i < m:
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length            # the match extends by one
            i += 1
        elif length != 0:
            length = lps[length - 1]   # fall back to the next shorter candidate; i stays
        else:
            lps[i] = 0
            i += 1
    return lps

for pat in ["ababc", "aaaa", "abacabad"]:
    print(pat, "→", " ".join(map(str, compute_lps(pat))))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> computeLps(const string& pat) {
    int m = pat.size();
    vector<int> lps(m, 0);
    int len = 0;                           // length of the previous longest prefix-suffix
    int i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) {
            lps[i++] = ++len;              // the match extends by one
        } else if (len != 0) {
            len = lps[len - 1];            // fall back to the next shorter candidate; i stays
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

int main() {
    for (string pat : {"ababc", "aaaa", "abacabad"}) {
        cout << pat << " →";
        for (int x : computeLps(pat)) cout << " " << x;
        cout << "\n";
    }
}

Java

public class Main {
    static int[] computeLps(String pat) {
        int m = pat.length();
        int[] lps = new int[m];
        int len = 0;                           // length of the previous longest prefix-suffix
        int i = 1;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) {
                lps[i++] = ++len;              // the match extends by one
            } else if (len != 0) {
                len = lps[len - 1];            // fall back to the next shorter candidate; i stays
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }

    public static void main(String[] args) {
        for (String pat : new String[]{"ababc", "aaaa", "abacabad"}) {
            StringBuilder sb = new StringBuilder(pat + " →");
            for (int x : computeLps(pat)) sb.append(" ").append(x);
            System.out.println(sb);
        }
    }
}

JavaScript

function computeLps(pat) {
    const m = pat.length;
    const lps = new Array(m).fill(0);
    let len = 0;                               // length of the previous longest prefix-suffix
    let i = 1;
    while (i < m) {
        if (pat[i] === pat[len]) {
            lps[i++] = ++len;                  // the match extends by one
        } else if (len !== 0) {
            len = lps[len - 1];                // fall back to the next shorter candidate; i stays
        } else {
            lps[i++] = 0;
        }
    }
    return lps;
}

for (const pat of ["ababc", "aaaa", "abacabad"])
    console.log(pat, "→", computeLps(pat).join(" "));

Output

ababc → 0 0 1 2 0
aaaa → 0 1 2 3
abacabad → 0 0 1 0 1 2 3 0

Time O(m) · Space O(m)

KMP string matching

The text index i never goes back; only the pattern index j falls back

txt :  a a a a a b a a a a a c
pat :  a a a a                  j = 4 = m → report 0, j = lps[3] = 3
pat :    a a a a                txt[4] = a = pat[3] → j = 4 → report 1, j = 3
pat :      a a a a              txt[5] = b ≠ pat[3] → j = lps[2] = 2 … → j = 0, then i++
pat :              a a a a      matches resume at i = 6 → report 6, then 7

Python

def compute_lps(pat):
    lps = [0] * len(pat)
    length, i = 0, 1
    while i < len(pat):
        if pat[i] == pat[length]:
            length += 1
            lps[i] = length
            i += 1
        elif length != 0:
            length = lps[length - 1]
        else:
            lps[i] = 0
            i += 1
    return lps

def kmp_search(txt, pat):
    n, m = len(txt), len(pat)
    lps = compute_lps(pat)
    res = []
    i = j = 0                          # i → text, j → pattern
    while i < n:
        if txt[i] == pat[j]:
            i += 1
            j += 1
            if j == m:                 # full match ends at i-1
                res.append(i - j)
                j = lps[j - 1]         # keep going: overlapping matches
        elif j != 0:
            j = lps[j - 1]             # fall back in the pattern; i does not move
        else:
            i += 1                     # no partial match to reuse
    return res

for txt, pat in [("abcdefg", "bcd"), ("aaaaab", "aaaa"), ("aaaaabaaaaac", "aaaa")]:
    print(pat, "in", txt, "→", " ".join(map(str, kmp_search(txt, pat))))

C++

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> computeLps(const string& pat) {
    int m = pat.size();
    vector<int> lps(m, 0);
    int len = 0, i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) lps[i++] = ++len;
        else if (len != 0) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

vector<int> kmpSearch(const string& txt, const string& pat) {
    int n = txt.size(), m = pat.size();
    vector<int> lps = computeLps(pat), res;
    int i = 0, j = 0;                          // i → text, j → pattern
    while (i < n) {
        if (txt[i] == pat[j]) {
            i++; j++;
            if (j == m) {                      // full match ends at i-1
                res.push_back(i - j);
                j = lps[j - 1];                // keep going: overlapping matches
            }
        } else if (j != 0) {
            j = lps[j - 1];                    // fall back in the pattern; i does not move
        } else {
            i++;                               // no partial match to reuse
        }
    }
    return res;
}

string join(const vector<int>& v) {
    string s;
    for (size_t i = 0; i < v.size(); i++) s += (i ? " " : "") + to_string(v[i]);
    return s;
}

int main() {
    vector<pair<string, string>> tests = {{"abcdefg", "bcd"}, {"aaaaab", "aaaa"}, {"aaaaabaaaaac", "aaaa"}};
    for (auto& [txt, pat] : tests)
        cout << pat << " in " << txt << " → " << join(kmpSearch(txt, pat)) << "\n";
}

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static int[] computeLps(String pat) {
        int m = pat.length();
        int[] lps = new int[m];
        int len = 0, i = 1;
        while (i < m) {
            if (pat.charAt(i) == pat.charAt(len)) lps[i++] = ++len;
            else if (len != 0) len = lps[len - 1];
            else lps[i++] = 0;
        }
        return lps;
    }

    static List<Integer> kmpSearch(String txt, String pat) {
        int n = txt.length(), m = pat.length();
        int[] lps = computeLps(pat);
        List<Integer> res = new ArrayList<>();
        int i = 0, j = 0;                          // i → text, j → pattern
        while (i < n) {
            if (txt.charAt(i) == pat.charAt(j)) {
                i++; j++;
                if (j == m) {                      // full match ends at i-1
                    res.add(i - j);
                    j = lps[j - 1];                // keep going: overlapping matches
                }
            } else if (j != 0) {
                j = lps[j - 1];                    // fall back in the pattern; i does not move
            } else {
                i++;                               // no partial match to reuse
            }
        }
        return res;
    }

    static String join(List<Integer> v) {
        StringBuilder sb = new StringBuilder();
        for (int x : v) sb.append(sb.length() == 0 ? "" : " ").append(x);
        return sb.toString();
    }

    public static void main(String[] args) {
        String[][] tests = {{"abcdefg", "bcd"}, {"aaaaab", "aaaa"}, {"aaaaabaaaaac", "aaaa"}};
        for (String[] t : tests)
            System.out.println(t[1] + " in " + t[0] + " → " + join(kmpSearch(t[0], t[1])));
    }
}

JavaScript

function computeLps(pat) {
    const m = pat.length, lps = new Array(m).fill(0);
    let len = 0, i = 1;
    while (i < m) {
        if (pat[i] === pat[len]) lps[i++] = ++len;
        else if (len !== 0) len = lps[len - 1];
        else lps[i++] = 0;
    }
    return lps;
}

function kmpSearch(txt, pat) {
    const n = txt.length, m = pat.length;
    const lps = computeLps(pat), res = [];
    let i = 0, j = 0;                              // i → text, j → pattern
    while (i < n) {
        if (txt[i] === pat[j]) {
            i++; j++;
            if (j === m) {                         // full match ends at i-1
                res.push(i - j);
                j = lps[j - 1];                    // keep going: overlapping matches
            }
        } else if (j !== 0) {
            j = lps[j - 1];                        // fall back in the pattern; i does not move
        } else {
            i++;                                   // no partial match to reuse
        }
    }
    return res;
}

for (const [txt, pat] of [["abcdefg", "bcd"], ["aaaaab", "aaaa"], ["aaaaabaaaaac", "aaaa"]])
    console.log(pat, "in", txt, "→", kmpSearch(txt, pat).join(" "));

Output

bcd in abcdefg → 1
aaaa in aaaaab → 0 1
aaaa in aaaaabaaaaac → 0 1 6 7

Time O(n + m) · Space O(m)

Anagram search

Does the text contain any permutation of the pattern as a substring? Order no longer matters, only the multiset of characters, so hashing by comparison fails and we count instead. Naive: for every window, count the pattern's characters up and the window's characters down and check that everything cancels.

Python — naive

CHAR = 256

def is_anagram_at(txt, pat, i):
    count = [0] * CHAR
    for j in range(len(pat)):
        count[ord(pat[j])] += 1
        count[ord(txt[i + j])] -= 1
    return all(c == 0 for c in count)

def contains_anagram(txt, pat):
    n, m = len(txt), len(pat)
    return any(is_anagram_at(txt, pat, i) for i in range(n - m + 1))

print("Yes" if contains_anagram("geeksforgeeks", "forg") else "No")
print("Yes" if contains_anagram("geeksforgeeks", "rseek") else "No")

Output

Yes
No

Time O((n − m + 1) · (m + CHAR)) · Space O(CHAR)

Python

CHAR = 256

def contains_anagram(txt, pat):
    n, m = len(txt), len(pat)
    if m > n:
        return False
    ct, cp = [0] * CHAR, [0] * CHAR
    for i in range(m):                     # first window and the pattern
        ct[ord(txt[i])] += 1
        cp[ord(pat[i])] += 1
    for i in range(m, n):
        if ct == cp:
            return True
        ct[ord(txt[i])] += 1               # character entering the window
        ct[ord(txt[i - m])] -= 1           # character leaving the window
    return ct == cp                        # the last window

for txt, pat in [("geeksforgeeks", "forg"), ("geeksforgeeks", "rseek"), ("cbaebabacd", "abc")]:
    print(pat, "in", txt, "→", "Yes" if contains_anagram(txt, pat) else "No")

C++

#include <array>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int CHAR = 256;

bool containsAnagram(const string& txt, const string& pat) {
    int n = txt.size(), m = pat.size();
    if (m > n) return false;
    array<int, CHAR> ct{}, cp{};
    for (int i = 0; i < m; i++) {                      // first window and the pattern
        ct[(unsigned char)txt[i]]++;
        cp[(unsigned char)pat[i]]++;
    }
    for (int i = m; i < n; i++) {
        if (ct == cp) return true;
        ct[(unsigned char)txt[i]]++;                   // character entering the window
        ct[(unsigned char)txt[i - m]]--;               // character leaving the window
    }
    return ct == cp;                                   // the last window
}

int main() {
    vector<pair<string, string>> tests = {{"geeksforgeeks", "forg"}, {"geeksforgeeks", "rseek"}, {"cbaebabacd", "abc"}};
    for (auto& [txt, pat] : tests)
        cout << pat << " in " << txt << " → " << (containsAnagram(txt, pat) ? "Yes" : "No") << "\n";
}

Java

import java.util.Arrays;

public class Main {
    static final int CHAR = 256;

    static boolean containsAnagram(String txt, String pat) {
        int n = txt.length(), m = pat.length();
        if (m > n) return false;
        int[] ct = new int[CHAR], cp = new int[CHAR];
        for (int i = 0; i < m; i++) {                  // first window and the pattern
            ct[txt.charAt(i)]++;
            cp[pat.charAt(i)]++;
        }
        for (int i = m; i < n; i++) {
            if (Arrays.equals(ct, cp)) return true;
            ct[txt.charAt(i)]++;                       // character entering the window
            ct[txt.charAt(i - m)]--;                   // character leaving the window
        }
        return Arrays.equals(ct, cp);                  // the last window
    }

    public static void main(String[] args) {
        String[][] tests = {{"geeksforgeeks", "forg"}, {"geeksforgeeks", "rseek"}, {"cbaebabacd", "abc"}};
        for (String[] t : tests)
            System.out.println(t[1] + " in " + t[0] + " → " + (containsAnagram(t[0], t[1]) ? "Yes" : "No"));
    }
}

JavaScript

const CHAR = 256;

function sameCounts(a, b) {
    for (let i = 0; i < CHAR; i++) if (a[i] !== b[i]) return false;
    return true;
}

function containsAnagram(txt, pat) {
    const n = txt.length, m = pat.length;
    if (m > n) return false;
    const ct = new Array(CHAR).fill(0), cp = new Array(CHAR).fill(0);
    for (let i = 0; i < m; i++) {                      // first window and the pattern
        ct[txt.charCodeAt(i)]++;
        cp[pat.charCodeAt(i)]++;
    }
    for (let i = m; i < n; i++) {
        if (sameCounts(ct, cp)) return true;
        ct[txt.charCodeAt(i)]++;                       // character entering the window
        ct[txt.charCodeAt(i - m)]--;                   // character leaving the window
    }
    return sameCounts(ct, cp);                         // the last window
}

for (const [txt, pat] of [["geeksforgeeks", "forg"], ["geeksforgeeks", "rseek"], ["cbaebabacd", "abc"]])
    console.log(pat, "in", txt, "→", containsAnagram(txt, pat) ? "Yes" : "No");

Output

forg in geeksforgeeks → Yes
rseek in geeksforgeeks → No
abc in cbaebabacd → Yes

Time O(n · CHAR) · Space O(CHAR)

Lexicographic rank of a string

Among all permutations of the string's characters listed in dictionary order, which position does the string itself hold (1-based)? For "ABC" the six permutations are:

Rank	Permutation
1	`ABC`
2	`ACB`
3	`BAC`
4	`BCA`
5	`CAB`
6	`CBA`

The pen-and-paper method generates every permutation and counts — O(n · n!):

Python — naive

from itertools import permutations

def rank_naive(s):
    perms = sorted(''.join(p) for p in permutations(s))     # n! strings, sorted
    return perms.index(s) + 1

print(rank_naive("ABC"), rank_naive("BAC"), rank_naive("STRING"))

Output

1 3 598

Rank of "BAC"

s = "BAC",  n = 3,  (n-1)! = 2

i = 0, 'B' : smaller unused chars = {A} → 1 × 2! = 2 permutations start with 'A'
i = 1, 'A' : smaller unused chars = {}  → 0 × 1! = 0
rank = 1 + 2 + 0 = 3

Python

CHAR = 256

def factorial(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r

def lex_rank(s):
    n = len(s)
    count = [0] * CHAR
    for ch in s:
        count[ord(ch)] += 1
    for c in range(1, CHAR):                 # cumulative: count[c] = #chars <= c
        count[c] += count[c - 1]
    rank = 1
    mul = factorial(n)
    for i in range(n - 1):
        mul //= n - i                        # (n - i - 1)!
        c = ord(s[i])
        rank += count[c - 1] * mul           # unused chars smaller than s[i]
        for j in range(c, CHAR):             # s[i] is used up now
            count[j] -= 1
    return rank

for s in ["ABC", "BAC", "CBA", "STRING"]:
    print(s, "→", lex_rank(s))

C++

#include <iostream>
#include <string>
using namespace std;

const int CHAR = 256;

long long factorial(int n) {
    long long r = 1;
    for (int i = 2; i <= n; i++) r *= i;
    return r;
}

long long lexRank(const string& s) {
    int n = s.size();
    int count[CHAR] = {0};
    for (char ch : s) count[(unsigned char)ch]++;
    for (int c = 1; c < CHAR; c++) count[c] += count[c - 1];   // cumulative: count[c] = #chars <= c
    long long rank = 1, mul = factorial(n);
    for (int i = 0; i < n - 1; i++) {
        mul /= n - i;                                    // (n - i - 1)!
        int c = (unsigned char)s[i];
        rank += count[c - 1] * mul;                      // unused chars smaller than s[i]
        for (int j = c; j < CHAR; j++) count[j]--;       // s[i] is used up now
    }
    return rank;
}

int main() {
    for (string s : {"ABC", "BAC", "CBA", "STRING"})
        cout << s << " → " << lexRank(s) << "\n";
}

Java

public class Main {
    static final int CHAR = 256;

    static long factorial(int n) {
        long r = 1;
        for (int i = 2; i <= n; i++) r *= i;
        return r;
    }

    static long lexRank(String s) {
        int n = s.length();
        int[] count = new int[CHAR];
        for (char ch : s.toCharArray()) count[ch]++;
        for (int c = 1; c < CHAR; c++) count[c] += count[c - 1];   // cumulative: count[c] = #chars <= c
        long rank = 1, mul = factorial(n);
        for (int i = 0; i < n - 1; i++) {
            mul /= n - i;                                    // (n - i - 1)!
            int c = s.charAt(i);
            rank += count[c - 1] * mul;                      // unused chars smaller than s[i]
            for (int j = c; j < CHAR; j++) count[j]--;       // s[i] is used up now
        }
        return rank;
    }

    public static void main(String[] args) {
        for (String s : new String[]{"ABC", "BAC", "CBA", "STRING"})
            System.out.println(s + " → " + lexRank(s));
    }
}

JavaScript

const CHAR = 256;

function factorial(n) {
    let r = 1;
    for (let i = 2; i <= n; i++) r *= i;
    return r;
}

function lexRank(s) {
    const n = s.length;
    const count = new Array(CHAR).fill(0);
    for (const ch of s) count[ch.charCodeAt(0)]++;
    for (let c = 1; c < CHAR; c++) count[c] += count[c - 1];   // cumulative: count[c] = #chars <= c
    let rank = 1, mul = factorial(n);
    for (let i = 0; i < n - 1; i++) {
        mul /= n - i;                                    // (n - i - 1)!  (exact: mul is a multiple)
        const c = s.charCodeAt(i);
        rank += count[c - 1] * mul;                      // unused chars smaller than s[i]
        for (let j = c; j < CHAR; j++) count[j]--;       // s[i] is used up now
    }
    return rank;
}

for (const s of ["ABC", "BAC", "CBA", "STRING"])
    console.log(s, "→", lexRank(s));

Output

ABC → 1
BAC → 3
CBA → 6
STRING → 598

Time O(n · CHAR) · Space O(CHAR)

Longest substring with distinct characters

Find the length of the longest substring in which no character repeats. The naive version tests every substring; the better one notices that once a substring from i contains a repeat, no longer substring from i can be distinct — so it breaks out of the inner loop.

Python — naive O(n³) and better O(n²)

def longest_distinct_naive(s):                 # O(n^3): every (i, j), each checked in O(n)
    n, best = len(s), 0
    for i in range(n):
        for j in range(i, n):
            if len(set(s[i:j + 1])) == j - i + 1:
                best = max(best, j - i + 1)
    return best

def longest_distinct_better(s):                # O(n^2): extend from i until the first repeat
    n, best = len(s), 0
    for i in range(n):
        seen = set()
        for j in range(i, n):
            if s[j] in seen:
                break
            seen.add(s[j])
            best = max(best, j - i + 1)
    return best

print(longest_distinct_naive("abcdabc"), longest_distinct_better("abcdabc"))
print(longest_distinct_naive("geeksforgeeks"), longest_distinct_better("geeksforgeeks"))

Output

4 4
7 7

The window start only ever moves right

s     :  a  b  c  d  a  b  c
j = 4 : 'a' last seen at 0 → start = 1, window "bcda" (length 4)
j = 5 : 'b' last seen at 1 → start = 2, window "cdab" (length 4)
j = 6 : 'c' last seen at 2 → start = 3, window "dabc" (length 4)

Python

def longest_distinct(s):
    prev = [-1] * 256                 # last index where each character was seen
    start = 0                         # left end of the current distinct window
    best = 0
    for j, ch in enumerate(s):
        start = max(start, prev[ord(ch)] + 1)   # jump past the previous occurrence
        best = max(best, j - start + 1)
        prev[ord(ch)] = j
    return best

for s in ["abcdabc", "aaa", "geeksforgeeks", "abcdefg"]:
    print(s, "→", longest_distinct(s))

C++

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;

int longestDistinct(const string& s) {
    int prev[256];
    fill(prev, prev + 256, -1);                  // last index where each character was seen
    int start = 0, best = 0;                     // start = left end of the current distinct window
    int n = s.size();
    for (int j = 0; j < n; j++) {
        unsigned char ch = s[j];
        start = max(start, prev[ch] + 1);        // jump past the previous occurrence
        best = max(best, j - start + 1);
        prev[ch] = j;
    }
    return best;
}

int main() {
    for (string s : {"abcdabc", "aaa", "geeksforgeeks", "abcdefg"})
        cout << s << " → " << longestDistinct(s) << "\n";
}

Java

import java.util.Arrays;

public class Main {
    static int longestDistinct(String s) {
        int[] prev = new int[256];
        Arrays.fill(prev, -1);                       // last index where each character was seen
        int start = 0, best = 0;                     // start = left end of the current distinct window
        for (int j = 0; j < s.length(); j++) {
            char ch = s.charAt(j);
            start = Math.max(start, prev[ch] + 1);   // jump past the previous occurrence
            best = Math.max(best, j - start + 1);
            prev[ch] = j;
        }
        return best;
    }

    public static void main(String[] args) {
        for (String s : new String[]{"abcdabc", "aaa", "geeksforgeeks", "abcdefg"})
            System.out.println(s + " → " + longestDistinct(s));
    }
}

JavaScript

function longestDistinct(s) {
    const prev = new Array(256).fill(-1);            // last index where each character was seen
    let start = 0, best = 0;                         // start = left end of the current distinct window
    for (let j = 0; j < s.length; j++) {
        const ch = s.charCodeAt(j);
        start = Math.max(start, prev[ch] + 1);       // jump past the previous occurrence
        best = Math.max(best, j - start + 1);
        prev[ch] = j;
    }
    return best;
}

for (const s of ["abcdabc", "aaa", "geeksforgeeks", "abcdefg"])
    console.log(s, "→", longestDistinct(s));

Output

abcdabc → 4
aaa → 1
geeksforgeeks → 7
abcdefg → 7

Time O(n) · Space O(CHAR)

Interview Q&A

KMP or Rabin–Karp — when do you pick which?

What exactly does lps[i] mean, and why is it the right amount to fall back?

Why is KMP O(n + m) when it has a loop that does not advance i?

The Rabin–Karp hash matched but the strings differ — is the algorithm wrong?

How would you return the anagram positions instead of Yes/No, and the substring instead of the length?

Lexicographic rank with repeated characters?