字符串的子字符串的順序統計

我有一個長字符串s的大小爲n和整數i。根據字典順序，我對s的i子字符串感興趣。字符串的子字符串的順序統計

天真的方法是創建s的所有子串的集合，然後獲得該集合的第n階統計量。此方法需要O(n^2)時間，但構建s的所有子串的集合的方式太內存密集。

有沒有更多的「記憶友好」的方法？

2012-02-25 Randomblue

如果」子「你的意思是你的輸入字符串中任何連續字符的子集，那麼確實存在O（n^2）這樣的字符串。你需要研究多少個索引？我想你需要一個固定數量的（例如1），因爲如果你需要所有可能的索引，那麼計算時間需要對所有的子串進行排序，這需要O（n^2 log n）而不是O（n^2）。這是一個正確的猜測？ – EOL 2012-02-25 02:11:15

@EOL用於查找大小爲n的列表中的元素的標準quickselect算法是O（n），而不是O（n log（n））。 – btilly 2012-02-25 06:51:48

@ btilly：確實。 O（n^2 log n）是排序（天真地）排列所有子串的時間複雜度 - 與O（n^2）相比，它僅爲單個i找到第i個字符串。 – EOL 2012-02-25 07:37:26

子字符串是字符串後綴的前綴。您可以使用http://en.wikipedia.org/wiki/Suffix_array中提到的算法之一在時間O（n）中獲得後綴的排序列表。 JuhaKärkkäinen和Peter Sanders（2003）提到的那個。「簡單的線性工作後綴數組結構是相當簡單的。

從後綴的排序列表某種懶合併方案應該讓你後綴的前綴的排序列表=子的排序列表。

來源

2012-02-25 05:27:35 mcdowella

這裏是獲得第i個字符串中的起始字符的方式：

s = "robert" 

cumulative = 0 
for c,num in sorted((j,i+1) for i,j in enumerate(reversed(s))): 
    print c,num,cumulative 
    cumulative+=x 

b 4 0 
e 3 4 
o 5 7 
r 2 12 
r 6 14 
t 1 20

從上面（這可以快速生成），你可以從累計值看結果

現在，如果我是間0和4，我們應該使用'b'作爲第一個字符。如果我在7到12之間，我們會用'o'作爲第一個字符，等等。

爲了驗證這一點，我們可以看看有序子串（請參閱7和12之間，他們都開始用「O」）（從索引0開始，包含了7，獨家12）：

print sorted([s[a:b] for a in range(n+1) for b in range(a+1,n+2)]) 
['b', 'be', 'ber', 'bert', 'e', 'er', 'ert', 'o', 'ob', 'obe', 'ober', 'obert', 'r', 'r', 'ro', 'rob', 'robe', 'rober', 'robert', 'rt', 't']

現在你可以使用這種技術來獲得第一個字符。一旦你有第一個字符，你從累計值知道你已經過去了多少個子串。我們可以從i中減去這個累計值。現在我們看一個第一個（之前選擇的）字符（不包括第一個字符）的新字符串。我們再次應用相同的技巧（使用新的字符串和新的i值）來獲得第二個字符。

希望這是有道理的。祝你好運。

來源

2012-02-25 01:57:38

@Randomblue這對你有意義嗎？ – 2012-02-25 02:36:03

如果有重複的字符，則會增加複雜性。您必須檢查每個重複字符的子字符串重疊多少。 – 2012-02-25 04:07:24

字符串的子字符串的順序統計

回答

相關問題