주어진 문자열에 대해 모든 고유 한 하위 문자열 생성
문자열이 주어지면 s
모든 고유 하위 문자열 집합을 생성하는 가장 빠른 방법은 무엇입니까?
예 : str = "aba"
우리는 substrs={"a", "b", "ab", "ba", "aba"}
.
순진한 알고리즘은 1..n
각 반복 에서 길이의 부분 문자열을 생성하는 전체 문자열을 순회하여 O(n^2)
상한을 산출하는 것 입니다.
더 나은 바운드가 가능합니까?
(이것은 기술적으로 숙제이므로 포인터 만 사용하는 것도 환영합니다)
다른 포스터가 말했듯이 주어진 문자열에 대해 잠재적으로 O (n ^ 2) 하위 문자열이 있으므로 인쇄가 그보다 빨리 수행 될 수 없습니다. 그러나 선형 시간으로 구성 할 수있는 집합의 효율적인 표현이 있습니다 . 접미사 트리 .
문자열에 총 O (n 2 ) 하위 문자열 이 있기 때문에 O (n 2 ) 보다 빠르게이 작업을 수행 할 수있는 방법이 없습니다 . 따라서 모두 생성해야하는 경우 해당 숫자는 최악의 경우가됩니다.
O (n
2 )
Ω (n 2 ) 의
상한
.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)
바퀴를 재창조 할 필요가 없습니다. 현이 아니라 세트를 기반으로하므로 개념을 가져와 자신의 상황에 적용해야합니다.
알고리즘
음, 잠재적으로 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
'Development Tip' 카테고리의 다른 글
문자열에 null을 합법적으로 추가하는 이유는 무엇입니까? (0) | 2020.11.28 |
---|---|
JDBC를 사용하여 .sql 스크립트 파일을 실행하는 방법 (0) | 2020.11.28 |
"if __name__ == '__main__'"콘텐츠를 테스트하거나 모의하는 방법 (0) | 2020.11.28 |
데이터베이스에 구애받지 않는 Play 애플리케이션을 작성하고 최초 데이터베이스 초기화를 수행하는 방법은 무엇입니까? (0) | 2020.11.28 |
왜`std :: initializer_list`는 종종 값으로 전달됩니까? (0) | 2020.11.28 |