为给定字符串生成所有唯一的子字符串
为给定字符串生成所有唯一的子字符串
提问于 2010-04-01 20:28:07
给定一个字符串s，什么方法可以最快地生成一组其所有唯一的子字符串？
例如:对于str = "aba"，我们会得到substrs={"a", "b", "ab", "ba", "aba"}。
朴素的算法是遍历整个字符串，在每次迭代中生成长度为1..n的子串，产生O(n^2)上限。
有没有可能有更好的边界？
(从技术上讲，这是家庭作业，所以也欢迎只使用指针)
回答 11
Stack Overflow用户
回答已采纳
发布于 2010-04-01 21:46:37
正如其他发帖者所说，对于给定的字符串，可能有O(n^2)个子字符串，因此打印它们的速度不能比这更快。然而，存在一个可以在线性时间内构造的集合的有效表示：the suffix tree。
Stack Overflow用户
发布于 2013-09-05 04:46:59
第一种是蛮力算法，复杂度为O(N^3)；第二种算法使用HashSet，算法复杂度为O(N^2)；第三种算法通过初始查找给定字符串的所有后缀，其最坏情况为O(N^2)，最佳情况为O(N Log(N))。
第一个解决方案：
import java.util.Scanner;
public class DistinctSubString {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Enter The string");
String s = in.nextLine();
long startTime = System.currentTimeMillis();
int L = s.length();
int N = L * (L + 1) / 2;
String[] Comb = new String[N];
for (int i = 0, p = 0; i < L; ++i) {
for (int j = 0; j < (L - i); ++j) {
Comb[p++] = s.substring(j, i + j + 1);
}
}
/*
* for(int j=0;j<N;++j) { System.out.println(Comb[j]); }
*/
boolean[] val = new boolean[N];
for (int i = 0; i < N; ++i)
val[i] = true;
int counter = N;
int p = 0, start = 0;
for (int i = 0, j; i < L; ++i) {
p = L - i;
for (j = start; j < (start + p); ++j) {
if (val[j]) {
//System.out.println(Comb[j]);
for (int k = j + 1; k < start + p; ++k) {
if (Comb[j].equals(Comb[k])) {
counter--;
val[k] = false;
}
}
}
}
start = j;
}
System.out.println("Substrings are " + N
+ " of which unique substrings are " + counter);
long endTime = System.currentTimeMillis();
System.out.println("It took " + (endTime - startTime) + " milliseconds");
}
}第二种解决方案：
import java.util.*;
public class DistictSubstrings_usingHashTable {
public static void main(String args[]) {
// create a hash set
Scanner in = new Scanner(System.in);
System.out.print("Enter The string");
String s = in.nextLine();
int L = s.length();
long startTime = System.currentTimeMillis();
Set<String> hs = new HashSet<String>();
// add elements to the hash set
for (int i = 0; i < L; ++i) {
for (int j = 0; j < (L - i); ++j) {
hs.add(s.substring(j, i + j + 1));
}
}
System.out.println(hs.size());
long endTime = System.currentTimeMillis();
System.out.println("It took " + (endTime - startTime) + " milliseconds");
}
}第三种解决方案：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class LCPsolnFroDistinctSubString {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter Desired String ");
String string = br.readLine();
int length = string.length();
String[] arrayString = new String[length];
for (int i = 0; i < length; ++i) {
arrayString[i] = string.substring(length - 1 - i, length);
}
Arrays.sort(arrayString);
for (int i = 0; i < length; ++i)
System.out.println(arrayString[i]);
long num_substring = arrayString[0].length();
for (int i = 0; i < length - 1; ++i) {
int j = 0;
for (; j < arrayString[i].length(); ++j) {
if (!((arrayString[i].substring(0, j + 1)).equals((arrayString)[i + 1]
.substring(0, j + 1)))) {
break;
}
}
num_substring += arrayString[i + 1].length() - j;
}
System.out.println("unique substrings = " + num_substring);
}
}第四种解决方案：
public static void printAllCombinations(String soFar, String rest) {
if(rest.isEmpty()) {
System.out.println(soFar);
} else {
printAllCombinations(soFar + rest.substring(0,1), rest.substring(1));
printAllCombinations(soFar , rest.substring(1));
}
}
Test case:- printAllCombinations("", "abcd");Stack Overflow用户
发布于 2010-04-01 20:36:54
为了大哦..。你能做的最多是O(n^2)
不需要重新发明轮子，它不是基于字符串，而是基于集合，所以你必须将这些概念应用到你自己的情况中。
算法
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2560262
复制相关文章
相似问题