Class StringUtilities

Generic utilities and extensions for strings.

Inheritance

System.Object

StringUtilities

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: MoreStructures.Utilities

Assembly: MoreStructures.dll

Syntax

public static class StringUtilities

Methods

LongestCommonPrefix(IEnumerable<Char>, IEnumerable<Char>)

Returns the length of the longest prefix in common between the provided of System.Char.

Declaration

public static int LongestCommonPrefix(IEnumerable<char> enumerable1, IEnumerable<char> enumerable2)

Parameters

Type	Name	Description
IEnumerable<System.Char>	enumerable1
IEnumerable<System.Char>	enumerable2

Returns

Type	Description
System.Int32	An integer betwen 0 and the length of the shortest of the enumerables provided.

Remarks

ALGORITHM
- The algorithm iterates over two enumerators in parallel, one enumerator per enumerable provided.
- It keeps running the enumerators until one of the two is over, or the current items of the two enumerators are different.
- It keeps a counter of the number of chars found equal from the beginning, which is returned as result.

COMPLEXITY
- Enumerator creation, moving to next item and accessing the current item are all constant-time operations.
- If the two enumerables have length l1 and l2 respectively, there are at most max(l1, l2) iterations.
- The current item of each enumerable has a constant size.
- If l1 and l2 are O(n), Time Complexity is O(n) and Space Complexity is O(1).

LongestCommonPrefix(String, Int32, String, Int32)

Returns the length of the longest prefix in common between the substrings of the provided System.String instances, starting at the provided indexes.

Declaration

public static int LongestCommonPrefix(string string1, int index1, string string2, int index2)

Parameters

Type	Name	Description
System.String	string1
System.Int32	index1
System.String	string2
System.Int32	index2

Returns

Type	Description
System.Int32	An integer betwen 0 and the length of the shortest of the strings provided, minus related starting index.

Remarks

ADVANTAGES AND DISADVANTAGES
- While LongestCommonPrefix(s1, i1, s2, i2) is conceptually equivalent to LongestCommonPrefix(s1.Skip(i1), s2.Skip(i2)), making use of the general implementation of LCP given by LongestCommonPrefix(IEnumerable<Char>, IEnumerable<Char>), this specific implementation, with System.String instances and System.Int32 starting indexes, has been provided.
- The reason behind the decision of providing a specialized implementation is that the LINQ method is O(n), rather than O(1).
- Moreover, the performance "suboptimality" cannot be overcome by using ranges on System.String: LongestCommonPrefix(s1[i1..], s2[i2..]) builds two new strings, s1[i1..] and s2[i2..], by copying the part of the underlying arrays of s1 and s2 starting at index i1 and i2 respectively. This results in s1[i1..] and s2[i2..] being O(n) both in time and space.
- Check https://stackoverflow.com/questions/6742923/, and the answer from Eric Lippert, for further information about the performance of substring extraction from a System.String instance.

ALGORITHM
- The algorithm iterates over two strings in parallel, each from the provided index.
- It keeps checking chars from the two strings until one of the two strings is over, or the current char of the two strings are different.
- It keeps a counter of the number of chars found equal from the beginning, which is returned as result.

COMPLEXITY
- Direct char accessm on a string, as well as checking its length, are constant-time operations.
- If the two strings have length l1 and l2 respectively, and starting indexes are i1 and i2 respectively, there are at most max(l1 - i1, l2 - i2) iterations.
- If l1, i1, l2 and i2 are O(n), Time Complexity is O(n) and Space Complexity is O(1).