Generate all unique substrings for given string

Solution 1:

As other posters have said, there are potentially O(n^2) substrings for a given string, so printing them out cannot be done faster than that. However there exists an efficient representation of the set that can be constructed in linear time: the suffix tree.

Solution 2:

There is no way to do this faster than O(n²) because there are a total of O(n²) substrings in a string, so if you have to generate them all, their number will be n(n + 1) / 2 in the worst case, hence the upper lower bound of O(n²) Ω(n²).

Solution 3:

First one is brute force which has complexity O(N^3) which could be brought down to O(N^2 log(N)) Second One using HashSet which has Complexity O(N^2) Third One using LCP by initially finding all the suffix of a given string which has the worst case O(N^2) and best case O(N Log(N)).

First Solution:-

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");
  }
}

Second Solution:-

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");
  }
}

Third Solution:-

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);
  }

}

Fourth Solution:-

  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");