实习第二天，被老员工欺负，躲在厕所哭。。

今天我又碰到了一个有意思的算法题，题目是这样的：找出给定字符串中的所有不同的循环子字符串。

在说题解之前，我们先了解一下什么是循环子字符串。简单来说，循环子字符串就是指通过循环移动字符串中的字符，得到的所有不同的子串。举个例子，假如有字符串“abc”，那么它的循环子字符串包括：

• "abc"
• "bca"
• "cab"

这也就是所有通过移位得到的不同子串。

想要搞清楚这个问题，我们首先得知道如何生成这些循环子字符串，然后去重它们。理论上，如果要暴力解法的话，可以先通过每个字符作为起点，拼接出所有的循环子串，最后放到一个集合里去重。听起来似乎没问题，但如果输入的字符串非常长，显然这个方法的时间复杂度会很高，我们需要一个更加高效的方案。

接下来我就给大家讲讲这个问题如何用 Java 代码来实现。我们从最简单的暴力解法说起：

import java.util.HashSet;
import java.util.Set;

publicclassMain{
publicstatic Set<String> getDistinctCircularSubstrings(String str){
        Set<String> result = new HashSet<>();
int len = str.length();
for (int i = 0; i < len; i++) {
for (int j = i + 1; j <= len; j++) {
                String substring = str.substring(i, j);
                String rotated = substring;
for (int k = 0; k < substring.length(); k++) {
                    rotated = rotated.substring(1) + rotated.charAt(0);
                    result.add(rotated);
                }
            }
        }
return result;
    }

publicstaticvoidmain(String[] args){
        String str = "abc";
        Set<String> result = getDistinctCircularSubstrings(str);
        System.out.println("Different circular substrings: " + result);
    }
}

这个暴力方法通过双重循环，分别从每个起点开始获取子串，再通过循环生成所有可能的子字符串。看上去好像没啥问题，运行起来也没毛病。但是，如果字符串的长度变大，效率就成了一个大问题，尤其是我们在每次获取子串的时候都在做字符串拼接，时间复杂度可不低啊。

那么怎么优化呢？如果我们能通过字符串的一些性质来避免多次重复计算，就可以显著提升效率。实际上，我们可以利用一个巧妙的数学技巧，避免手动循环生成所有的子串。

比如说，给定字符串abc，如果我们将字符串本身连接到它自己上，得到abcabc，那么这个新的字符串中，所有的子串都会包含原始字符串的所有循环子串。这是一个非常聪明的技巧，因为通过将字符串拼接一遍，我们就可以直接获取所有的循环子串，而不需要每次都去做移位操作。

让我们看一下这个优化版的代码实现：

import java.util.HashSet;
import java.util.Set;

publicclassMain{
publicstatic Set<String> getDistinctCircularSubstrings(String str){
        Set<String> result = new HashSet<>();
        String doubledStr = str + str;  // 拼接字符串自己
int len = str.length();

for (int i = 0; i < len; i++) {
for (int j = i + 1; j <= i + len; j++) {
                result.add(doubledStr.substring(i, j));  // 直接从拼接后的字符串中截取
            }
        }
return result;
    }

publicstaticvoidmain(String[] args){
        String str = "abc";
        Set<String> result = getDistinctCircularSubstrings(str);
        System.out.println("Different circular substrings: " + result);
    }
}

这段代码的关键在于，我们将原始字符串和它自己拼接成了一个新的字符串。这样，doubledStr就包含了所有循环子串的信息。通过遍历这个拼接后的字符串，我们只需要简单地截取所有长度为 n 的子串即可，而不需要每次进行字符的旋转操作了。这样，程序的效率大大提高，特别是在字符串长度较大时，优势更加明显。

这个方法的时间复杂度是 O(n²)，其中 n 是字符串的长度。相比之前的暴力方法，显然性能要好得多。而且这个方法也避免了不必要的字符串拼接，减少了额外的空间开销。

总结一下，虽然问题本身看似简单，但要解决它，还是得用点小技巧，像字符串拼接这种“巧妙”的方式，能够让问题变得更加简单。