Functions for finding repeated substrings. More...

Functions
auto	csd::longest_repeated_substring (const char *sv, size_t len) -> std::string
	Find the longest repeated non-overlapping substring.

Detailed Description

Functions for finding repeated substrings.

Function Documentation

◆ longest_repeated_substring()

auto csd::longest_repeated_substring	(	const char *	sv,
		size_t	len
	)		-> std::string

extern

Find the longest repeated non-overlapping substring.

This function finds the longest substring that appears at least twice in the input string, with the constraint that the occurrences must not overlap. It uses a dynamic programming approach with optimized space complexity.

The algorithm builds a 2D table where each cell [i][j] stores the length of the longest common substring ending at positions i-1 and j-1, but only if the substrings don't overlap (j-i > lcsre[i-1][j-1]).

Example:

longest_repeated_substring("banana", 6) returns "an"
// "an" appears at positions 1-2 and 3-4 (non-overlapping)
 
longest_repeated_substring("abcabcabc", 9) returns "abc"
// "abc" appears at positions 0-2, 3-5, and 6-8
 
longest_repeated_substring("abcdef", 6) returns ""
// No repeated substrings found

Parameters

[in]	sv	Pointer to a null-terminated character array representing the input string. The string should contain valid ASCII or UTF-8 characters.
[in]	len	Length of the input string. Must be non-negative and should match the actual length of the string (excluding null terminator).

Returns: The longest repeated non-overlapping substring found. If no repeated substring exists, returns an empty string.

Exceptions

std::invalid_argument If sv is nullptr or if len doesn't match the actual string length.

Note: Time complexity: O(n^2) where n is the string length; Space complexity: O(n) due to row-wise table optimization