Java找出两个字符串中所有共同的子串。
时间: 2024-05-03 09:20:35 浏览: 9
您好!关于您的问题,要找出两个字符串中所有共同的子串,可以采用暴力匹配法,对于其中一个字符串,逐个截取所有长度相同的子串,然后在另一个字符串中查找是否存在相同的子串,找到则记录下来即可。
代码示例:
```java
public static List<String> findCommonSubstrings(String s1, String s2) {
List<String> commonSubstrings = new ArrayList<>();
for (int i = 0; i < s1.length(); i++) {
for (int j = i + 1; j <= s1.length(); j++) {
String substring = s1.substring(i, j);
if (s2.indexOf(substring) != -1) {
commonSubstrings.add(substring);
}
}
}
return commonSubstrings;
}
```
注意,以上仅为一种常见的解法,实际上还存在更高效的算法,例如动态规划和后缀树等。
相关问题
用IDEA用字符串操作找出两个字符串中最大子字符串,
可以使用动态规划(DP)来解决这个问题。具体步骤如下:
1. 创建一个二维数组 dp,其中 dp[i][j] 表示第一个字符串前 i 个字符与第二个字符串前 j 个字符的最长公共子串的长度。
2. 初始化 dp 数组的第一行和第一列,都为0。
3. 遍历第一个字符串中的每个字符和第二个字符串中的每个字符,如果这两个字符相等,则 dp[i][j] = dp[i-1][j-1] + 1。
4. 如果这两个字符不相等,则 dp[i][j] = 0。
5. 在遍历的过程中,记录最长公共子串的长度和结束位置。
6. 最后根据结束位置和最长公共子串的长度可以得到最大子字符串。
下面是使用 Java 代码实现该算法:
``` java
public static String longestCommonSubstring(String str1, String str2) {
int m = str1.length();
int n = str2.length();
int[][] dp = new int[m+1][n+1];
int maxLength = 0;
int endPosition = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1.charAt(i-1) == str2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
if (dp[i][j] > maxLength) {
maxLength = dp[i][j];
endPosition = i;
}
} else {
dp[i][j] = 0;
}
}
}
return str1.substring(endPosition - maxLength, endPosition);
}
```
以上代码时间复杂度为 O(mn),空间复杂度为 O(mn)。
java给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度
可以使用滑动窗口的方法来解决这个问题。具体来说,我们使用两个指针表示字符串中的某个子串(的左右边界)。其中左指针代表着上文中「枚举子串的起始位置」,而右指针即为上文中的 rrk。
在每一步的操作中,我们会将左指针向右移动一格,表示我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;在枚举结束后,我们找到的最长的子串的长度即为答案。
时间复杂度:O(n),其中 n 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
代码如下:
```java
public int lengthOfLongestSubstring(String s) {
int n = s.length();
Set<Character> set = new HashSet<>();
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
ans = Math.max(ans, j - i);
} else {
set.remove(s.charAt(i++));
}
}
return ans;
}
```