Java 中计算字符串中不同子串的数量

给定一个字符串 inStr。任务是计算字符串 inStr 的唯一子串的总数。输入字符串的所有字符都是小写字母。

示例 1

输入

String inStr = "abcde"

输出: 有 16 个唯一子串。

解释: 不同的子串是: "", "a", "b", "c", "d", "e", "ab", "bc", "cd", "de", "abc", "bcd", "cde", "abcd", "bcde", "abcde" 它们的数量是 16。因此，输出是 16。

示例 2

输入

String inStr = "abbcccdd"

输出: 有 32 个唯一子串。

解释: 不同的子串是: "", "a", "b", "c", "d", "ab", "bb", "bc", "cc", "cd", "dd", "abb", "bbc", "bcc", "ccc", "ccd", "cdd", "abbc", "bbcc", "bccc", "cccd", "ccdd", "abbcc", "bbccc" "bcccd", "cccdd", "abbccc", "bbcccd", "bcccdd", "abbcccd", "bbcccdd", "abbcccdd" 它们的数量是 32。因此，输出是 32。

示例 3

输入

String inStr = "aaaaaaa"

输出: 有 8 个唯一子串。

解释: 不同的子串是: "", "a", "aa", "aaa", "aaaa", "aaaaa", "aaaaaa", "aaaaaaa" 它们的数量是 8。因此，输出是 8。

方法：使用 Substring() 方法

方法很简单。我们所要做的就是使用嵌套的 for 循环和 substring() 方法生成给定字符串的所有子字符串。生成的子字符串可以放入哈希集合中。因此，所有重复的子字符串都会被丢弃，因为哈希集合始终包含唯一元素。哈希集合的大小就是我们的答案。

文件名: DistinctSubArrCount.java

输出

For the string: "abcde", the total substring count is: 16 

For the string: "abbcccdd", the total substring count is: 32 

For the string: "aaaaaaa", the total substring count is: 8

复杂度分析: 嵌套的 for 循环需要 O(n²) 的时间来完成工作。此外，我们在内部 for 循环中调用 substring() 方法，而 substring() 方法需要 O(n) 的时间。因此，程序的总时间复杂度为 O(n³)。该程序还使用哈希集合来存储子字符串。字符串的数量最多可以达到 (n x (n + 1)) / 2，子字符串的大小最多可以达到 n。因此，程序的空间复杂度为 O(n³)，其中 n 是输入字符串中存在的字符总数。

优化: 我们可以排除使用 substring() 方法来降低程序的时空复杂度。我们可以将当前字符追加到前一个子字符串以生成当前子字符串。

文件名: DistinctSubArrCount1.java

输出

For the string: "abcde", the total substring count is: 16 

For the string: "abbcccdd", the total substring count is: 32 

For the string: "aaaaaaa", the total substring count is: 8

复杂度分析: 该程序仅使用嵌套的 for 循环。因此，程序的时空复杂度为 O(n²)。空间复杂度与前一个程序相同。

由于较高的空间复杂度，上述程序不适合处理大型字符串。对于大型字符串，上述程序会给出 MLE (内存限制超出)。因此，需要进行一些优化来减少程序消耗的内存。

方法：使用 TRIE

可以使用 TRIE 来改进空间复杂度。方法是仅将那些尚未插入的字符插入到 TRIE 中。当出现这样的字符时，意味着我们将得到唯一的子串，我们将唯一子串的数量加 1。请看下面的实现。

文件名: DistinctSubArrCount2.java

输出

For the string: "abcde", the total substring count is: 16 

For the string: "abbcccdd", the total substring count is: 32 

For the string: "aaaaaaa", the total substring count is: 8

复杂度分析: 程序的时间复杂度与前一个程序相同。对于每一个尚未存储在 TRIE 数据结构中的字符，我们需要分配 26 个字符的内存，这使得程序的空间复杂度为 O(26 x n)，我们也可以将其写成渐近的 O(n)。