주어진 문자열에 대해 모든 고유 한 하위 문자열 생성

주어진 문자열에 대해 모든 고유 한 하위 문자열 생성

---

문자열이 주어지면 s모든 고유 하위 문자열 집합을 생성하는 가장 빠른 방법은 무엇입니까?

예 : str = "aba"우리는 substrs={"a", "b", "ab", "ba", "aba"}.

순진한 알고리즘은 1..n각 반복 에서 길이의 부분 문자열을 생성하는 전체 문자열을 순회하여 O(n^2)상한을 산출하는 것 입니다.

더 나은 바운드가 가능합니까?

(이것은 기술적으로 숙제이므로 포인터 만 사용하는 것도 환영합니다)

---

다른 포스터가 말했듯이 주어진 문자열에 대해 잠재적으로 O (n ^ 2) 하위 문자열이 있으므로 인쇄가 그보다 빨리 수행 될 수 없습니다. 그러나 선형 시간으로 구성 할 수있는 집합의 효율적인 표현이 있습니다 . 접미사 트리 .

---

문자열에 총 O (n ² ) 하위 문자열 이 있기 때문에 O (n ² ) 보다 빠르게이 작업을 수행 할 수있는 방법이 없습니다 . 따라서 모두 생성해야하는 경우 해당 숫자는 최악의 경우가됩니다. O (n ² ) Ω (n ² ) 의 상한 .n(n + 1) / 2

---

첫 번째는 복잡성이 O (N ^ 3) 인 무차별 대입으로 O (N ^ 2 log (N))로 내려갈 수 있습니다. 두 번째는 복잡성이 O (N ^ 2) 인 HashSet을 사용하는 것입니다. 최악의 경우 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의 정말 좋은 백서

심층 파워 포인트

문자열 파마 블로그

---

음, 잠재적으로 n*(n+1)/2다른 부분 문자열 (빈 부분 문자열의 경우 +1)이 있기 때문에 O(n*2)(최악의 경우) 보다 나을 수 있을지 의심 됩니다. 가장 쉬운 방법은 그것들을 생성하고 O(1)당신이 그것들을 찾을 때 바로 중복을 제외하기 위해 멋진 룩업 테이블 (해시 맵과 같은)을 사용하는 것입니다.

---

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

---

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

---

문자열의 고유 한 하위 문자열의 총 개수는 n (n + 1) / 2가되기 때문에 o (n ^ 2) 시간에만 수행 할 수 있습니다.

예:

문자열 s = "abcd"

pass 0 : (모든 문자열의 길이가 1 임)

a, b, c, d = 4 개 스트링

패스 1 : (모든 문자열의 길이가 2 임)

ab, bc, cd = 3 개 문자열

패스 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"를 함수에 전달하면 다음 결과가 생성됩니다.

a, ab, abc, abcd, abcde, abcdef, abcdf, abce, abcef, abcf, abd, abde, abdef, abdf, abe, abef, abf, ac, acd, acde, acdef, acdf, ace, acef, acf, ad, ade, adef, adf, ae, aef, af, b, bc, bcd, bcde, bcdef, bcdf, bce, bcef, bcf, bd, bde, bdef, bdf, be, bef, bf, c, cd, cde, cdef, cdf, ce, cef, cf, d, de, def, df, e, ef, f

---

Naive 알고리즘은 O (n ^ 2) 시간 대신 O (n ^ 3) 시간이 걸립니다. O (n ^ 2) 개의 하위 문자열이 있습니다. 그리고 O (n ^ 2) 개의 부분 문자열 (예 : set)을 넣으면 set은 각 문자열에 대한 O (lgn) 비교를 비교하여 세트에 존재하는지 여부를 확인합니다. 게다가 문자열 비교에는 O (n) 시간이 걸립니다. 따라서 set를 사용하면 O (n ^ 3 lgn) 시간이 걸립니다. set 대신 hashtable을 사용하면 O (n ^ 3) 시간을 줄일 수 있습니다.

요점은 숫자 비교가 아니라 문자열 비교입니다.

따라서 가장 좋은 알고리즘 중 하나는 접미사 배열과 LCP (Longest Common Prefix) 알고리즘을 사용하면이 문제에 대한 O (n ^ 2) 시간을 줄여줍니다. O (n) 시간 알고리즘을 사용하여 접미사 배열을 만듭니다. LCP = O (n) 시간에 대한 시간. 접미사 배열의 각 문자열 쌍에 대해 LCP를 수행하여 총 시간이 O (n ^ 2) 시간이되어 별개의 하위 트링 의 길이 를 찾습니다 .

모든 고유 한 하위 문자열 을 인쇄 하려면 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] = '\0';
            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;
}

Both algorithms listed a simply too slow for extremely long strings though. I tested the algorithms against a string of length over 47,000 and the algorithms took over 20 minutes to complete, with the first one taking 1200 seconds, and the second one taking 1360 seconds, and that's just counting the unique substrings without outputting to the terminal. So for probably strings of length up to 1000 you might get a working solution. Both solutions did compute the same total number of unique substrings though. I did test both algorithms against string lengths of 2000 and 10,000. The times were for the first algorithm: 0.33 s and 12 s; for the second algorithm it was 0.535 s and 20 s. So it looks like in general the first algorithm is faster.

---

Many answers that include 2 for loops and a .substring() call claim O(N^2) time complexity. However, it is important to note that the worst case for a .substring() call in Java (post update 6 in Java 7) is O(N). So by adding a .substring() call in your code, the order of N has increased by one.

Therefore, 2 for loops and a .substring() call within those loops equals an O(N^3) time complexity.

---

Your programs are not giving unique sbstrins.

Please test with input abab and output should be aba,ba,bab,abab.

참고URL : https://stackoverflow.com/questions/2560262/generate-all-unique-substrings-for-given-string