DSA

Big-O notation and complexity analysis Core

Big-O describes how the work an algorithm does grows as the input grows, ignoring constant factors. O(1) is constant, O(log n) halves the problem each step, O(n) touches each item once, O(n log n) is typical of good sorting, O(n²) compares pairs, and O(2ⁿ) tries every subset. Analyse time and space, and usually the worst case.

To analyse code, count how often the innermost work runs: two nested loops over n is O(n²), a loop that halves its range is O(log n). Know amortised cost (appending to a dynamic array is O(1) on average even though an occasional resize is O(n)) and that recursion uses stack space proportional to its depth.

Practice. Write down the time and space complexity of five solutions you have already written, then check each with a colleague or by timing it on growing inputs.

Recursion Core

A recursive function solves a problem by calling itself on smaller inputs until it reaches a base case it can answer directly. Every recursive solution needs three things: the base case, a step that makes the problem smaller, and trust that the smaller call returns the right answer.

Analyse recursion with a recurrence or a recursion tree: a function that calls itself twice on n minus 1 does O(2ⁿ) work, while one that halves the input once per call does O(log n). Deep recursion can overflow the call stack, so know how to convert to an explicit stack, and know when to add memoisation because the same subproblem repeats.

Practice. Write recursive functions for power and for reversing a list, then solve Pow(x, n) and Reverse Linked List recursively.

Choosing a language and its standard library Core

Use the language you write most fluently. Python is concise and popular for interviews; Java and C++ are common and fast; JavaScript is fine, especially for front-end roles. What matters is knowing the standard library well enough not to reinvent it.

Learn, for your language: dynamic arrays and slicing, hash maps and sets, a double-ended queue, a heap or priority queue, sorting with a custom key, string building, and integer limits. In Python that means list, dict, set, collections.deque, Counter, defaultdict and heapq; in Java, ArrayList, HashMap, ArrayDeque and PriorityQueue.

Practice. Write a one-page cheat sheet of the ten library calls you use most in your chosen language, with their complexity.

Practising effectively Recommended

How you practise matters more than how much. Learn one pattern at a time: read the idea, solve three to five problems that use it, then mix it with earlier patterns. Struggle honestly for 20 to 30 minutes before looking at a hint, and only read the full solution after a second attempt.

Keep a log of every problem with the pattern, the key insight and your mistake. Revisit problems after one day, one week and one month; the practice workspace's review schedule does this for you. Explain solutions out loud, because that is what the interview asks for.

Practice. Pick three problems you solved a month ago and solve them again from scratch without notes.

Arrays and dynamic arrays Core

An array stores items in contiguous memory, so reading by index is O(1) and scanning is fast. Dynamic arrays grow by allocating a larger block and copying, which keeps appends O(1) amortised. Inserting or deleting in the middle shifts everything after it, costing O(n).

Common techniques: in-place updates to save memory, iterating from the end when you write into the same array, swapping to partition, and using the array's own indices as a hash when values are in the range 1 to n. Watch for off-by-one errors at the boundaries and for modifying a list while iterating over it.

Practice. Solve Move Zeroes in place, then First Missing Positive using the array itself as a hash.

Strings Core

Strings are arrays of characters, but in many languages they are immutable, so building a string by repeated concatenation can cost O(n²). Collect pieces in a list and join once, or use a string builder.

Know how to count characters with a fixed-size array or a hash map, compare strings by sorted characters or counts for anagram problems, reverse words, check palindromes from both ends, and parse numbers safely. Clarify the character set: lowercase letters only, ASCII, or full Unicode changes the data structure and the memory cost.

Practice. Solve Valid Palindrome and Backspace String Compare without building new strings.

Two pointers Core

Two pointers walk through a sequence together to avoid nested loops. In the opposite ends form, one starts at each end of a sorted array and they move inwards based on a comparison, as in finding a pair with a target sum in O(n). In the same direction form, a slow pointer marks where to write and a fast pointer reads, as in removing duplicates in place.

The pattern works because sorted order tells you which pointer to move: if the sum is too small, only moving the left pointer can increase it. Combine with sorting for three-sum style problems, giving O(n²) instead of O(n³).

Practice. Solve Squares of a Sorted Array with two pointers from the ends, then 3Sum and Container With Most Water.

Sliding window Core

A sliding window keeps a contiguous range and moves its ends instead of recomputing from scratch. Fixed-size windows add the new element and remove the old one each step. Variable-size windows grow the right end, and shrink the left end while the window breaks a rule, recording the best valid window.

left = 0
for right, x in enumerate(items):
    add(x)
    while window_invalid():
        remove(items[left]); left += 1
    best = max(best, right - left + 1)

Each element enters and leaves the window once, so the whole scan is O(n). Use a hash map for counts inside the window, or a monotonic deque when you need the window's maximum or minimum.

Practice. Solve Longest Substring Without Repeating Characters with a variable window, then Minimum Window Substring, then Sliding Window Maximum with a deque that keeps candidates in decreasing order.

Prefix sums Core

A prefix sum array stores the running total, so the sum of any range is a subtraction: prefix[j + 1] - prefix[i], in O(1) after O(n) setup. Two-dimensional prefix sums do the same for rectangles in a grid.

Combined with a hash map of earlier prefix values, prefix sums count subarrays with a given sum in O(n): at each position, look up how many earlier prefixes equal the current prefix minus the target. The same trick handles subarrays with equal numbers of two values, by treating one as plus one and the other as minus one.

Practice. Solve Subarray Sum Equals K with prefix sums and a hash map, and explain why a sliding window fails when values can be negative. Then solve Contiguous Array.

Sorting and its uses Core

Know the main algorithms: merge sort (O(n log n), stable, extra memory), quicksort (O(n log n) on average, in place, O(n²) worst case), heap sort, and counting or bucket sort for small integer ranges in O(n + k). Comparison sorts cannot beat O(n log n).

In interviews you rarely implement a sort, but you constantly sort as a first step: to use two pointers, to group equal items, to sweep intervals, or to make greedy choices. Learn custom comparators, and remember sorting costs O(n log n), which may already be the target complexity.

Practice. Solve Sort Colors in one pass, then Largest Number with a custom comparator, and explain why comparing a+b with b+a is the right rule.

Hash maps and hash sets Core

A hash map stores key and value pairs and finds a key in O(1) on average, by computing a hash that points to a bucket. A hash set stores just keys. They are the single most useful tool in coding interviews: they turn many O(n²) searches into O(n).

Know their limits: no ordering, O(n) worst case when many keys collide, and keys must be immutable or hashable. Typical uses are remembering what you have seen (the pair-sum problem), mapping values to indices, deduplicating and caching results.

Practice. Solve Two Sum in one pass with a hash map from value to index, then Insert Delete GetRandom O(1).

Counting and grouping Core

Many problems reduce to counting: character frequencies for anagrams, the most common element, or whether one collection can be built from another. Use a counter or a fixed array when the alphabet is small.

Grouping uses a canonical key: the sorted letters of a word group anagrams together, a tuple of counts groups strings with equal character frequencies, and a normalised shape groups islands with the same shape. Choosing the right key is the whole problem.

Practice. Solve Valid Anagram, then Group Anagrams with a canonical key, and state the complexity for n words of length k.

Hashing for sequences and strings Recommended

Sets also answer questions about sequences quickly. To find the longest run of consecutive numbers in O(n), put all numbers in a set and start counting only from numbers whose predecessor is missing. To detect duplicates within a distance k, keep a sliding set of the last k values.

For strings, a rolling hash lets you compare substrings in O(1) after preprocessing, which powers substring search and finding repeated substrings. Mention collision risk and how to reduce it with a second hash.

Practice. Solve Longest Consecutive Sequence in O(n) with a set, then Palindrome Pairs using a hash map from reversed words to indices.

Linked lists Core

A linked list is a chain of nodes, each pointing to the next. Inserting or removing at a known node is O(1), but finding a node by position is O(n). Interview problems test careful pointer handling: reversing a list, merging sorted lists, removing the n-th node from the end and reordering.

Two habits prevent most bugs: use a dummy head node so the first node needs no special case, and draw the pointers before and after each step. Reversal needs three variables: previous, current and next.

Practice. Solve Reverse Linked List and Merge Two Sorted Lists, then Reorder List, which combines finding the middle, reversing and merging.

Fast and slow pointers Core

Two pointers moving at different speeds reveal structure in a linked list without extra memory. A slow pointer moving one step and a fast pointer moving two will meet if there is a cycle; when fast reaches the end, slow is at the middle.

To find where a cycle starts, after they meet move one pointer to the head and advance both one step at a time; they meet at the cycle's start. The same idea finds a duplicate number in an array whose values point to indices.

Practice. Solve Linked List Cycle and Middle of the Linked List, then use the middle in Sort List to split the list for merge sort.

Stacks Core

A stack is last in, first out. Use it whenever the most recent item must be handled first: matching brackets, undo, evaluating expressions, and simulating recursion. Push opening brackets and pop when a closing bracket arrives; the string is valid if every pop matches and the stack ends empty.

Stacks also evaluate postfix expressions directly and convert recursive tree traversals into loops. In most languages a dynamic array works as a stack with append and pop at the end.

Practice. Solve Valid Parentheses and Evaluate Reverse Polish Notation with a single stack each, then Min Stack.

Monotonic stack Recommended

A monotonic stack keeps its elements in increasing or decreasing order. When a new element breaks the order, you pop elements, and each pop is the moment you learn that element's answer, such as its next greater element.

Every element is pushed and popped once, so the scan is O(n). Use it for next greater or smaller element, daily temperature waits, stock spans, the largest rectangle in a histogram and trapping rain water. Store indices rather than values so you can compute distances.

Practice. Solve Daily Temperatures with a decreasing stack of indices, then Largest Rectangle in Histogram.

Queues and deques Core

A queue is first in, first out, and is the engine of breadth-first search. A deque supports O(1) operations at both ends; use it as a queue in BFS, and as a monotonic deque to keep the maximum or minimum of a sliding window.

Know how to build a queue from two stacks (amortised O(1) per operation) and a stack from queues, which are common warm-up questions, and when to use a circular buffer for a fixed-size queue.

Practice. Solve Implement Queue using Stacks and explain why each element is moved at most twice.

Binary search on sorted data Core

Binary search halves the search range each step, finding an item in a sorted array in O(log n). The hard part is the boundaries. Pick one template and use it always: for example, search for the first index where a condition becomes true, with lo and hi meaning the answer is in the half-open range.

lo, hi = 0, len(a)
while lo < hi:
    mid = (lo + hi) // 2
    if condition(a[mid]): hi = mid
    else: lo = mid + 1
return lo   # first index where condition holds

Variants find the first or last occurrence, the insertion point, or search a rotated sorted array by checking which half is sorted.

Practice. Solve Binary Search and First Bad Version with the same template, then Search in Rotated Sorted Array.

Binary search on the answer Core

When a problem asks for the minimum or maximum value that satisfies a condition, and the condition is monotonic (if a value works, every larger value works), you can binary search over the answer itself. Each step runs a check, often greedy and O(n), so the total is O(n log range).

Classic examples: the minimum ship capacity to deliver packages in d days, the minimum eating speed to finish in h hours, or the largest minimum distance when placing items. The skill is spotting the monotonic condition and writing the check function.

Practice. Find the minimum capacity to ship weights within d days by binary searching the capacity, then try Find K Closest Elements.

Searching in structures Recommended

Binary search also works on matrices sorted by row and column, on timestamps stored per key, and on any function that changes once from false to true. Sorted lists with binary search give simple versioned key-value stores where each lookup finds the latest value at or before a time.

When the search space is implicit, define clearly what lo and hi mean and what the loop returns, and test with one and two elements, where off-by-one errors show up.

Practice. Solve Search a 2D Matrix as one sorted list, then Time Based Key-Value Store with a sorted list of timestamps per key.

Binary trees and depth-first traversal Core

A binary tree is nodes with up to two children. Depth-first traversals visit nodes in preorder (node, left, right), inorder (left, node, right) or postorder (left, right, node). Most tree problems are a recursive function that combines answers from the left and right subtrees: height, diameter, path sums, balanced checks.

Decide what each call returns and what it records globally. The diameter problem, for example, returns the height of a subtree and updates a global best with left height plus right height. Practise writing traversals iteratively with a stack too, because some interviewers ask.

Practice. Solve Maximum Depth of Binary Tree, Diameter of Binary Tree and Binary Tree Maximum Path Sum, each with one recursive function.

Breadth-first traversal and level order Core

Breadth-first search visits a tree level by level using a queue. Processing the queue in batches of its current size gives you each level separately, which answers questions like the right side view, level averages, zigzag order and the width of each level.

Breadth-first search also finds the shortest path in unweighted structures, so it reappears in graphs. Converting a tree into a graph with parent links lets you search outward from any node.

Practice. Solve Binary Tree Level Order Traversal, Binary Tree Right Side View and Binary Tree Zigzag Level Order Traversal, then All Nodes Distance K in Binary Tree.

Binary search trees Core

In a binary search tree, every node's left subtree holds smaller values and its right subtree larger ones, so search, insert and delete take O(height): O(log n) if balanced, O(n) if not. An inorder traversal visits values in sorted order, which solves validation and k-th smallest problems.

Know how to validate a BST by passing down allowed ranges, find the lowest common ancestor by comparing values, and build a balanced tree from a sorted array by choosing the middle as the root.

Practice. Solve Validate Binary Search Tree and Kth Smallest Element in a BST, then Convert Sorted Array to Binary Search Tree and explain why choosing the middle keeps it balanced.

Serialisation and tree construction Recommended

Some problems ask you to turn a tree into a string and back, or to rebuild a tree from two traversals. Preorder with markers for missing children is enough to rebuild a tree uniquely; inorder plus preorder also determines it when values are distinct.

These problems test careful recursion with a shared index or an iterator over tokens. Explain the format you choose and why it is unambiguous.

Practice. Solve Construct Binary Tree from Preorder and Inorder Traversal, then Serialize and Deserialize Binary Tree with a preorder format and again with a level-order format.

Tries Recommended

A trie stores strings character by character in a tree, so all words with a common prefix share a path. Insert and search take O(L) for a word of length L, and prefix queries are natural, which makes tries ideal for autocomplete, word games and dictionary matching.

Each node holds a map or fixed array of children and an end-of-word flag. Wildcard search explores all children at a wildcard character. Tries can use a lot of memory, so mention compressed tries for large dictionaries.

Practice. Solve Implement Trie (Prefix Tree), then Design Add and Search Words Data Structure with depth-first search for wildcards, then Word Search II.

Heaps and top k Core

A heap gives the smallest (or largest) item in O(1) and inserts or removes in O(log n). To keep the k largest items from a stream, use a min-heap of size k and pop when it grows past k; the result costs O(n log k) instead of sorting everything.

Other uses: the k closest points, scheduling by priority, and the running median with two heaps (a max-heap for the lower half and a min-heap for the upper half, kept balanced). Most languages provide a min-heap; negate values or use a comparator for a max-heap.

Practice. Solve Kth Largest Element in an Array and Top K Frequent Words with a size-k heap, then Find Median from Data Stream with two heaps.

K-way merge Recommended

Merging k sorted lists efficiently uses a heap holding the current head of each list. Pop the smallest, append it, and push the next item from the same list. Each of n items is pushed and popped once, so the total is O(n log k).

The same pattern finds the smallest range covering an element from each list, and the k-th smallest element across sorted rows of a matrix.

Practice. Solve Merge k Sorted Lists with a heap, then by merging pairs of lists, and compare the complexity. Then try Smallest Range Covering Elements from K Lists.

Intervals Core

Interval problems almost always start by sorting by start time. Then sweep: merge an interval into the previous one if they overlap, otherwise start a new one. Inserting a new interval is the same sweep with three phases: before, overlapping and after.

For the minimum number of meeting rooms, sort start and end times separately and sweep, or keep a min-heap of end times. Clarify whether intervals that touch at an endpoint overlap; it changes one comparison.

Practice. Solve Merge Intervals and Insert Interval, then Meeting Rooms II and Employee Free Time.

Greedy algorithms Core

A greedy algorithm makes the locally best choice at each step and never reconsiders. It is fast and simple, but only correct when you can argue that a greedy choice never blocks an optimal solution, often by an exchange argument: any optimal solution can be changed to include the greedy choice without getting worse.

Classic greedy problems: choosing the most non-overlapping intervals by earliest end time, jump game reachability, gas station circuits and assigning tasks with cooldowns. When you cannot justify the greedy choice, the problem probably needs dynamic programming.

Practice. Solve Jump Game, Gas Station and Non-overlapping Intervals, and write one sentence for each explaining why the greedy choice is safe.

Graph representations and traversal Core

A graph is nodes connected by edges, directed or undirected, weighted or not. Store it as an adjacency list (a map from node to neighbours) for most problems; an adjacency matrix suits small dense graphs. Many problems hide a graph: a grid where cells are nodes, words that differ by one letter, or accounts linked by shared emails.

Depth-first search explores as far as possible before backtracking; breadth-first search explores level by level. Both visit every node and edge once, O(V + E). Always keep a visited set, and mark nodes when you add them to the queue, not when you pop them, to avoid duplicates.

Practice. Solve Number of Islands with both depth-first and breadth-first search, then Pacific Atlantic Water Flow by searching from the oceans inwards, and Clone Graph.

Shortest paths with breadth-first search Core

In an unweighted graph, breadth-first search finds the shortest path because it reaches nodes in order of distance. Track distance per node or process the queue level by level. Multi-source BFS starts with several nodes in the queue at once, solving problems like the time for rot to spread from many sources.

When the state includes more than position, such as remaining moves or keys collected, search over (position, extra) states. Count the states to make sure the search fits in time.

Practice. Solve Rotting Oranges with multi-source BFS and Shortest Path to Get Food with single-source BFS, then Minimum Knight Moves and Word Ladder.

Weighted shortest paths Recommended

Dijkstra's algorithm finds shortest paths with non-negative weights: repeatedly take the closest unfinished node from a min-heap and relax its edges, for O((V + E) log V). Bellman-Ford handles negative edges by relaxing all edges V minus 1 times, and detects negative cycles. Edges of weight 0 or 1 only can use a deque instead of a heap.

Limits on the number of steps change the problem: a cheapest route with at most k stops is solved by running k rounds of Bellman-Ford style relaxation, or BFS over (node, stops) states.

Practice. Solve Cheapest Flights Within K Stops with k rounds of relaxation, and explain why plain Dijkstra fails here.

Topological sort Core

A topological order lists the nodes of a directed acyclic graph so every edge points forwards. Kahn's algorithm repeatedly removes nodes with no incoming edges using a queue; if some nodes are never removed, there is a cycle. The depth-first version adds each node after its descendants and reverses the list.

Use it for course prerequisites, build orders, task scheduling and deriving an alphabet from a sorted list of words. Processing the queue level by level tells you which tasks can run in parallel.

Practice. Solve Course Schedule and Course Schedule II with Kahn's algorithm, then Alien Dictionary.

Union-find Recommended

Union-find (disjoint set union) tracks which elements are in the same group. find returns a group's representative and union merges two groups. With path compression and union by rank or size, both are nearly O(1).

It shines when edges arrive one at a time: counting connected components, detecting the edge that creates a cycle, merging accounts, and Kruskal's minimum spanning tree algorithm, which sorts edges by weight and adds each one that joins two different groups.

Practice. Solve Number of Connected Components in an Undirected Graph and Graph Valid Tree with union-find, then Accounts Merge.

Backtracking Core

Backtracking builds candidates one choice at a time and abandons a path as soon as it cannot lead to a valid answer. The template is: if the current path is complete, record it; otherwise, for each choice, make it, recurse, then undo it.

def backtrack(path, start):
    if done(path): result.append(path[:]); return
    for i in range(start, n):
        if not valid(i): continue
        path.append(choice(i))
        backtrack(path, i + 1)
        path.pop()

Use it for subsets, permutations, combinations with a target sum, word search in a grid and puzzles such as placing queens. Prune early, sort to skip duplicates, and state the exponential complexity honestly.

Practice. Solve Subsets, Permutations and Combination Sum with the same template, then Word Search and N-Queens.

Dynamic programming fundamentals Core

Dynamic programming solves problems with overlapping subproblems and optimal substructure by solving each subproblem once and reusing the answer. Define three things before writing code: the state (what a subproblem is, such as the best answer for the first i items), the transition (how a state is built from smaller ones) and the base cases.

Write it top-down as recursion with memoisation, which is often easiest to get right, or bottom-up by filling a table in order, which avoids recursion limits and can reduce memory by keeping only the last row. The complexity is the number of states times the work per state.

Practice. Solve Climbing Stairs top-down and bottom-up, then Decode Ways, and write the state and transition in one line each.

One-dimensional dynamic programming Core

Many problems have a state indexed by position: the best result for the first i elements. Examples are the maximum sum of non-adjacent houses, counting ways to reach a total, the minimum coins to make an amount, and the longest increasing subsequence (O(n²) with a table, or O(n log n) with binary search over tails).

Watch the difference between counting combinations and counting ordered sequences: the loop order changes the answer. Clarify which the problem wants.

Practice. Solve House Robber, Coin Change and Longest Increasing Subsequence, then Combination Sum IV and explain why it counts ordered sequences.

Grid and two-dimensional dynamic programming Core

Two-dimensional states cover grids and pairs of sequences. On grids: unique paths, minimum path sum and the largest square of ones, where each cell depends on its neighbours above and to the left. On two strings: the longest common subsequence and edit distance, where dp[i][j] describes the first i characters of one and j of the other.

Draw the table for a small example and fill it by hand; the transition usually becomes obvious. Most of these can drop to one row of memory.

Practice. Solve Unique Paths and Maximal Square, then Longest Increasing Path in a Matrix with memoised depth-first search.

Knapsack, intervals and bitmasks Optional

The 0/1 knapsack pattern chooses items under a capacity limit, with state (item, remaining capacity); iterate capacity downwards to use one row. Partition-into-equal-sums problems are knapsack in disguise. Interval dynamic programming works on ranges, such as bursting balloons or the cheapest way to merge stones, building answers from shorter ranges.

Bitmask dynamic programming stores a set of used items as bits when n is about 20 or less, as in visiting every city once. Recognise these from the input size table above.

Practice. Solve Partition Equal Subset Sum with a boolean knapsack table, then Word Break.

Bit manipulation Recommended

Know the operators AND, OR, XOR, NOT and shifts. Useful facts: x & (x - 1) clears the lowest set bit, so counting how often you can do it counts set bits; x & -x isolates the lowest set bit; XOR of a number with itself is zero, so XOR of all values finds the one that appears once.

Bitmasks represent small sets compactly for subsets and bitmask dynamic programming. Mind integer sizes and signed shifts in Java and C++, and Python's unbounded integers when emulating 32-bit behaviour.

Practice. Solve Single Number with XOR, then Number of 1 Bits and Counting Bits.

Maths and matrix problems Recommended

Common maths topics: greatest common divisor with Euclid's algorithm, primes with a sieve, fast exponentiation by squaring in O(log n), modular arithmetic to keep numbers small, and integer overflow checks. Reversing digits safely requires checking overflow before multiplying.

Matrix problems test index handling: rotating a square matrix in place by transposing and reversing rows, and spiral traversal by shrinking four boundaries. Write the boundary updates carefully and test on one-row and one-column matrices.

Practice. Solve Reverse Integer with overflow checks, then Rotate Image and Spiral Matrix.

Designing data structures Core

Some problems ask you to design a class with operations at stated complexities, such as an LRU cache with O(1) get and put. The approach: list each operation and its target cost, pick structures that give each cost, and keep them in sync. An LRU cache combines a hash map from key to node with a doubly linked list ordered by recency.

Other examples include a frequency stack, a hit counter over a time window, a randomised set and an in-memory file system. Explain the invariants each structure maintains and test every operation, including on an empty structure.

Practice. Solve LRU Cache, then Maximum Frequency Stack, Design Hit Counter and Design In-Memory File System.

Range queries: segment and Fenwick trees Optional

When you need range sums or minimums while values change, prefix sums are too slow to update. A Fenwick tree (binary indexed tree) supports point updates and prefix sums in O(log n) with a few lines of code. A segment tree supports any associative range query, such as minimum or maximum, and range updates with lazy propagation.

These appear in harder interviews and competitive programming. Know when they are needed and be able to write a Fenwick tree from memory.

Practice. Implement a Fenwick tree for point updates and range sums, and test it against a brute-force version on random inputs.

String algorithms Optional

Fast substring search avoids the O(n · m) brute force. The KMP algorithm precomputes, for each prefix of the pattern, the longest proper prefix that is also a suffix, so the search never moves backwards in the text: O(n + m). Rabin-Karp compares rolling hashes of windows. The Z-algorithm computes, for each position, the longest substring starting there that matches a prefix.

Palindrome problems use expand-around-centre in O(n²), which is usually enough in interviews. Mention linear-time algorithms only if asked.

Practice. Solve Longest Palindromic Substring by expanding around each centre, then implement KMP prefix-function search.