Сгенерируйте все уникальные подстроки для данной строки

нет способа сделать это быстрее, чем O (n²) потому что есть в общей сложности O (n²) подстроки в строке, так что если вам придется произвести их все их количество будет n(n + 1) / 2 в худшем случае, отсюда верхний нижняя граница O (n²) Ω (n²).

первый-это грубая сила, которая имеет сложность O (N^3) , которая может быть сведена к O (N^2 log(N)) Во-вторых, используя HashSet, который имеет сложность O (N^2) Третий использует 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");

большой ой ... Лучшее, что вы могли бы сделать, это O(n^2)

не нужно изобретать колесо, его не на основе строк, а на множествах, поэтому вам придется взять концепции и применить их к своей собственной ситуации.

алгоритмы

действительно хорошая белая бумага от MS

в глубине PowerPoint

блог на строку химической завивки

ну, так как там потенциально n*(n+1)/2 разные подстроки (+1 для пустой подстроки), я сомневаюсь, что вы можете быть лучше, чем O(n*2) (в худшем случае). самое простое-создать их и использовать некоторые хорошие O(1) таблица поиска (например, hashmap) для исключения дубликатов прямо при их поиске.

class program
{

        List<String> lst = new List<String>();
        String str = "abc";
        public void func()
        {

            subset(0, "");
            lst.Sort();
            lst = lst.Distinct().ToList();

            foreach (String item in lst)
            {
                Console.WriteLine(item);
            }
        }
        void subset(int n, String s)
        {
            for (int i = n; i < str.Length; i++)
            {
                lst.Add(s + str[i].ToString());
                subset(i + 1, s + str[i].ToString());
            }
        }
}

class SubstringsOfAString {
    public static void main(String args[]) {

        String string = "Hello", sub = null;

        System.out.println("Substrings of \"" + string + "\" are :-");

        for (int i = 0; i < string.length(); i++) {
            for (int j = 1; j <= string.length() - i; j++) {
                sub = string.substring(i, j + i);
                System.out.println(sub);
            }
        }
    }
}

Это можно сделать только за o(n^2) время, так как общее количество уникальных подстрок строки будет n(n+1)/2.

пример:

строка s = "abcd"

pass 0: (все строки имеют длину 1)

a, b, c, d = 4 строки

pass 1: (все строки имеют длину 2)

ab, bc, cd = 3 строки

pass 2: (все строки имеют длину 3)

abc, bcd = 2 строки

передача 3: (все строки имеют длину 4)

abcd = 1 строка

используя эту аналогию, мы можем написать решение с O(n^2) временной сложностью и постоянной пространственной сложностью.

исходный код выглядит следующим образом:

#include<stdio.h>

void print(char arr[], int start, int end)
{
    int i;
    for(i=start;i<=end;i++)
    {
        printf("%c",arr[i]);
    }
    printf("\n");
}


void substrings(char arr[], int n)
{
    int pass,j,start,end;
    int no_of_strings = n-1;

    for(pass=0;pass<n;pass++)
    {
        start = 0;
        end = start+pass;
        for(j=no_of_strings;j>=0;j--)
        {
            print(arr,start, end);
            start++;
            end = start+pass;
        }
        no_of_strings--;
    }

}

int main()
{   
    char str[] = "abcd";
    substrings(str,4);
    return 0;
}

вот мой код на Python. Он генерирует все возможные подстроки данной строки.

def find_substring(str_in):
    substrs = []
    if len(str_in) <= 1:
        return [str_in]

    s1 = find_substring(str_in[:1])
    s2 = find_substring(str_in[1:])

    substrs.append(s1)
    substrs.append(s2)
    for s11 in s1:
        substrs.append(s11)            
        for s21 in s2:            
            substrs.append("%s%s" %(s11, s21))

    for s21 in s2:
        substrs.append(s21)

    return set(substrs)

Если вы передадите функцию str_ = "abcdef", она выдаст следующие результаты:

а, АВ, АВС, АВСD, АБВГД, абвгде, abcdf, abce, abcef, abcf, Абд, Абде, abdef, abdf, Эйб, сайт abef, АБФ, ас, ДСА, acde, acdef, ВДА, туз, acef, АКФ, ад, аде, АДЕФ, АДФ, АЭ, АР, АФ, Б, БК, ОНД, право на изменения bcde, bcdef, bcdf, до н. э. коэффициенты bcef, КБК, БД, бдэ, bdef, БДФ, быть, БЭФ, БФ, кондиционер, CD, CDE, который cdef, ВПР, КП, КПЭ, кф, д, де, деф, ДФ, е, эф Ф

наивный алгоритм занимает O(n^3) времени вместо O (n^2) времени. Существует O(n^2) Количество подстрок. А если поставить O (n^2) Количество подстрок, например, установить, затем set сравнивает o (lgn) сравнения для каждой строки, чтобы проверить, если он alrady существует в наборе или нет. Кроме того, для сравнения строк требуется O(n) времени. Поэтому при использовании set требуется O(n^3 lgn) времени. и вы можете уменьшить его O (n^3) время, если вы используете hashtable вместо set.

дело в том, что это сравнение строк не числовые сравнения.

Итак, один из лучших алгоритмов, скажем, если вы используете суффикс-массив и самый длинный общий префикс (LCP) алгоритм, он уменьшает время O(n^2) для этой проблемы. Построение суффиксного массива с использованием алгоритма времени O(n). Время для LCP = o (n) время. Так как для каждой пары строк в суффиксном массиве, сделать LCP так общее время составляет O (n^2) время, чтобы найти длина различных вычитаний.

кроме того, если вы хотите print все различные подстроки, это занимает O (n^2) времени.

это печатает уникальные подстроки. https://ideone.com/QVWOh0

def uniq_substring(test):
    lista=[]
    [lista.append(test[i:i+k+1]) for i in range(len(test)) for k in
    range(len(test)-i) if test[i:i+k+1] not in lista and 
    test[i:i+k+1][::-1] not in lista]
    print lista

uniq_substring('rohit')
uniq_substring('abab')

['r', 'ro', 'roh', 'rohi', 'rohit', 'o', 'oh', 'ohi', 'ohit', 'h',   
'hi', 'hit', 'i', 'it', 't']
['a', 'ab', 'aba', 'abab', 'b', 'bab']

попробуйте этот код, используя суффиксный массив и самый длинный общий префикс. Он также может дать вам общее количество уникальных подстрок. Код может дать переполнение стека в visual studio, но отлично работает в Eclipse C++. Это потому, что он возвращает векторы для функций. Не проверял его против очень длинных строк. Сделаем так и отчитаемся.

  // C++ program for building LCP array for given text
#include <bits/stdc++.h>
#include <vector>
#include <string>
using namespace std;

#define MAX 100000
int cum[MAX];


// Structure to store information of a suffix
struct suffix
{
    int index; // To store original index
    int rank[2]; // To store ranks and next rank pair
};

// A comparison function used by sort() to compare two suffixes
// Compares two pairs, returns 1 if first pair is smaller
int cmp(struct suffix a, struct suffix b)
{
    return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):
        (a.rank[0] < b.rank[0] ?1: 0);
}

// This is the main function that takes a string 'txt' of size n as an
// argument, builds and return the suffix array for the given string
vector<int> buildSuffixArray(string txt, int n)
{
    // A structure to store suffixes and their indexes
    struct suffix suffixes[n];

    // Store suffixes and their indexes in an array of structures.
    // The structure is needed to sort the suffixes alphabatically
    // and maintain their old indexes while sorting
    for (int i = 0; i < n; i++)
    {
        suffixes[i].index = i;
        suffixes[i].rank[0] = txt[i] - 'a';
        suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;
    }

    // Sort the suffixes using the comparison function
    // defined above.
    sort(suffixes, suffixes+n, cmp);

    // At his point, all suffixes are sorted according to first
    // 2 characters. Let us sort suffixes according to first 4
    // characters, then first 8 and so on
    int ind[n]; // This array is needed to get the index in suffixes[]
    // from original index. This mapping is needed to get
    // next suffix.
    for (int k = 4; k < 2*n; k = k*2)
    {
        // Assigning rank and index values to first suffix
        int rank = 0;
        int prev_rank = suffixes[0].rank[0];
        suffixes[0].rank[0] = rank;
        ind[suffixes[0].index] = 0;

        // Assigning rank to suffixes
        for (int i = 1; i < n; i++)
        {
            // If first rank and next ranks are same as that of previous
            // suffix in array, assign the same new rank to this suffix
            if (suffixes[i].rank[0] == prev_rank &&
                    suffixes[i].rank[1] == suffixes[i-1].rank[1])
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = rank;
            }
            else // Otherwise increment rank and assign
            {
                prev_rank = suffixes[i].rank[0];
                suffixes[i].rank[0] = ++rank;
            }
            ind[suffixes[i].index] = i;
        }

        // Assign next rank to every suffix
        for (int i = 0; i < n; i++)
        {
            int nextindex = suffixes[i].index + k/2;
            suffixes[i].rank[1] = (nextindex < n)?
                                suffixes[ind[nextindex]].rank[0]: -1;
        }

        // Sort the suffixes according to first k characters
        sort(suffixes, suffixes+n, cmp);
    }

    // Store indexes of all sorted suffixes in the suffix array
    vector<int>suffixArr;
    for (int i = 0; i < n; i++)
        suffixArr.push_back(suffixes[i].index);

    // Return the suffix array
    return suffixArr;
}

/* To construct and return LCP */
vector<int> kasai(string txt, vector<int> suffixArr)
{
    int n = suffixArr.size();

    // To store LCP array
    vector<int> lcp(n, 0);

    // An auxiliary array to store inverse of suffix array
    // elements. For example if suffixArr[0] is 5, the
    // invSuff[5] would store 0. This is used to get next
    // suffix string from suffix array.
    vector<int> invSuff(n, 0);

    // Fill values in invSuff[]
    for (int i=0; i < n; i++)
        invSuff[suffixArr[i]] = i;

    // Initialize length of previous LCP
    int k = 0;

    // Process all suffixes one by one starting from
    // first suffix in txt[]
    for (int i=0; i<n; i++)
    {
        /* If the current suffix is at n-1, then we don’t
        have next substring to consider. So lcp is not
        defined for this substring, we put zero. */
        if (invSuff[i] == n-1)
        {
            k = 0;
            continue;
        }

        /* j contains index of the next substring to
        be considered to compare with the present
        substring, i.e., next string in suffix array */
        int j = suffixArr[invSuff[i]+1];

        // Directly start matching from k'th index as
        // at-least k-1 characters will match
        while (i+k<n && j+k<n && txt[i+k]==txt[j+k])
            k++;

        lcp[invSuff[i]] = k; // lcp for the present suffix.

        // Deleting the starting character from the string.
        if (k>0)
            k--;
    }

    // return the constructed lcp array
    return lcp;
}

// Utility function to print an array
void printArr(vector<int>arr, int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver program
int main()
{
    int t;
    cin >> t;
    //t = 1;

    while (t > 0)  {

        //string str = "banana";
        string str;

        cin >> str; // >> k;

        vector<int>suffixArr = buildSuffixArray(str, str.length());
        int n = suffixArr.size();

        cout << "Suffix Array : \n";
        printArr(suffixArr, n);

        vector<int>lcp = kasai(str, suffixArr);

        cout << "\nLCP Array : \n";
        printArr(lcp, n);

        // cum will hold number of substrings if that'a what you want (total = cum[n-1]
        cum[0] = n - suffixArr[0];

    //  vector <pair<int,int>> substrs[n];

        int count = 1;


        for (int i = 1; i <= n-suffixArr[0]; i++)  {
            //substrs[0].push_back({suffixArr[0],i});
            string sub_str = str.substr(suffixArr[0],i);
            cout << count << "  "  <<  sub_str << endl;
            count++;
        }

        for(int i = 1;i < n;i++)  {

            cum[i] = cum[i-1] + (n - suffixArr[i] - lcp[i - 1]);

            int end = n - suffixArr[i];
            int begin = lcp[i-1] + 1;
            int begin_suffix = suffixArr[i];

            for (int j = begin, k = 1; j <= end; j++, k++)  {

                //substrs[i].push_back({begin_suffix, lcp[i-1] + k});
        //      cout << "i push "  << i  << "   " << begin_suffix << " " << k << endl;
                string sub_str = str.substr(begin_suffix, lcp[i-1] +k);
                cout << count << "  "  <<  sub_str << endl;
                count++;

            }

        }

        /*int count = 1;

        cout << endl;

        for(int i = 0; i < n; i++){

            for (auto it = substrs[i].begin(); it != substrs[i].end(); ++it )    {

                string sub_str = str.substr(it->first, it->second);
                cout << count << "  "  <<  sub_str << endl;
                count++;
            }

        }*/


        t--;

    }

    return 0;
}

и вот более простой алгоритм:

#include <iostream>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
#include <time.h>

using namespace std;


char txt[100000], *p[100000];
int m, n;

int cmp(const void *p, const void *q) {
    int rc = memcmp(*(char **)p, *(char **)q, m);
    return rc;
}
int main() {
    std::cin >> txt;
    int start_s = clock();


    n = strlen(txt);
    int k; int i;
    int count = 1;
    for (m = 1; m <= n; m++) {
        for (k = 0; k+m <= n; k++)
            p[k] = txt+k;
        qsort(p, k, sizeof(p[0]), &cmp);
        for (i = 0; i < k; i++) {
            if (i != 0 && cmp(&p[i-1], &p[i]) == 0){
                continue;
            }
            char cur_txt[100000];
            memcpy(cur_txt, p[i],m);
            cur_txt[m] = '';
            std::cout << count << "  "  << cur_txt << std::endl;
            count++;
        }
    }

    cout << --count  << endl;

    int stop_s = clock();
    float run_time = (stop_s - start_s) / double(CLOCKS_PER_SEC);
    cout << endl << "distinct substrings  \t\tExecution time = " << run_time << " seconds" << endl;
    return 0;
}

оба алгоритма перечислены просто слишком медленно для очень длинных строк хотя. Я протестировал алгоритмы против строки длиной более 47 000, и алгоритмы заняли более 20 минут, чтобы завершить, причем первый из них занял 1200 секунд, а второй-1360 секунд, и это просто подсчет уникальных подстрок без вывода на терминал. Поэтому, вероятно, для строк длиной до 1000 вы можете получить рабочее решение. Однако оба решения вычисляли одинаковое общее количество уникальных подстрок. Я проверил оба алгоритма против длины строк 2000 и 10000. Времена были для первого алгоритма: 0,33 С и 12 С; для второго алгоритма это было 0,535 С и 20 С. Таким образом, похоже, что в целом первый алгоритм быстрее.

ваши программы не дают уникальные sbstrins.

пожалуйста, проверьте с ввод abab и выход должен быть!--1-->.