生成给定字符串的所有唯一子字符串

Question

给定一个字符串s,生成一组所有唯一子串的最快方法是什么？

示例:因为str = "aba"我们会得到substrs={"a", "b", "ab", "ba", "aba"}.

朴素算法将遍历1..n每个迭代中生成长度的子串的整个字符串,产生O(n^2)上限.

更好的约束可能吗？

(这是技术上的功课,所以也欢迎指针)

Answer 1

正如其他海报所说,对于给定的字符串,可能存在O(n ^ 2)子串,因此打印它们不能比这更快.然而,存在可以在线性时间内构造的集合的有效表示:后缀树.

Answer 2

没有办法比O(n ²)更快地执行此操作,因为字符串中总共有O(n ²)个子串,所以如果必须全部生成它们,那么它们的编号将是n(n + 1) / 2最坏的情况,因此上下限的为O(n ²) Ω(N ²).

Answer 3

第一个是具有复杂度O(N ^ 3)的蛮力,其可以使用具有复杂度O(N ^ 2)第三个的HashSet降低到O(N ^ 2 log(N))第二个使用LCP通过最初查找具有最坏情况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");