algorithm - Generate all unique substrings for given string -


given string s, fastest method generate set of unique substrings?

example: str = "aba" substrs={"a", "b", "ab", "ba", "aba"}.

the naive algorithm traverse entire string generating substrings in length 1..n in each iteration, yielding o(n^2) upper bound.

is better bound possible?

(this technically homework, pointers-only welcome well)

as other posters have said, there potentially o(n^2) substrings given string, printing them out cannot done faster that. there exists efficient representation of set can constructed in linear time: the suffix tree.


Comments

Post a Comment

Popular posts from this blog

android - How to save instance state of selected radiobutton on menu -

i have options menu in toolbar radibutton item : <item android:id="@+id/map_menu" android:icon="@drawable/ic_layer" android:orderincategory="102" app:showasaction="always" android:title="@string/action_settings"> <menu> <group android:id="@+id/map_types_group" android:checkablebehavior="single" > <item android:id="@+id/map_terrain" android:orderincategory="1" app:showasaction="ifroom" android:title="@string/map_terrain"/> <item android:id="@+id/map_normal" android:orderincategory="2" android:checked="true" app:showasaction="ifroom" android:title="@string/map_normal"/> ...
Read more

python 3 IndexError: list index out of range -

my problem average value on won't show returns error traceback (most recent call last): (file location), line 29, in <module> average_score = [[x[8],x[0]] x in a_list] (file location), line 29, in <listcomp> average_score = [[x[8],x[0]] x in a_list] indexerror: list index out of range the code import csv class_a = open('class_a.txt') csv_a = csv.reader(class_a) a_list = [] row in csv_a: row[3] = int(row[3]) row[4] = int(row[4]) row[5] = int(row[5]) minimum = min(row[3:5]) row.append(minimum) maximum = max(row[3:5]) row.append(maximum) average = sum(row[3:5])//3 row.append(average) a_list.append(row[0:8]) print(row[8]) this works when test out values 0 7 ,even if change location of avarage sum still error when call a_list.append(row[0:8]) you're appending array using indexes 0, 1, 2, 3, 4, 5, 6, , 7 row . means when later iterate a_list , x variable has indexes 7, , you're trying a...
Read more

IF statement in MySQL trigger -

this query code in mysql trigger. if 1=2 select 'yes'; else select 'no'; end if; but has following error: if '1'='2' select 'yes' error code: 1064. have error in sql syntax; check manual corresponds mysql server version right syntax use near 'if '1'='2' select 'yes'' @ line 1 0.000 sec what solution?
Read more