Decisionproblem上字符串

鑑於是一組S = {S 1 ，...，S_米}其中各s _我是長度爲k的在字母表{0,1} ,?一個字符串。Decisionproblem上字符串

我在尋找一種有效的算法求解以下決策問題：
這是真的，每次1 ≤一個< b ≤ķ有一個字符串s _我 S中S.T.小號_我（A）= 0和s _我（B）= 1或S _我（A）= 1和s _我（B）= 0，其中s _我的（a）表示字符串中的第一個字符s _i。

我在找m中的次線性時間算法，所以像O（\ sqrt（m）f（k））這樣的東西就是目標。

來源

2012-03-30 user695652

這個問題的原始格式讓我很難過，不像[CSTheory.SE]（http://cstheory.stackexchange.com），StackOverflow不支持[MathJax]（http://www.mathjax.org /）。 :( – MrGomez 2012-03-30 23:49:20

是的，格式化是非常痛苦的閱讀。 – DRVic 2012-03-30 23:57:30

我改變了它，對不起，我不知道，因此，不支持MathJax – user695652 2012-03-31 00:08:15

除非允許先前的離線處理，否則不能在小於線性時間內完成。

基本上，滿足您的標準的第一個字符串將是您考慮的最後一個字符串。你可能必須首先考慮所有m-1個人。

來源

2012-03-31 00:05:01 DRVic

但這運行在時間成正比m * k否？ – user695652 2012-03-31 00:13:29

更改答案以迴應改變的問題。原始問題有不可思議的格式並要求亞二次方，而不是亞線性。 – DRVic 2012-03-31 00:17:34

簡單。 BITFIELD你的性格空間（0 == 0x1，1 == 0x2，...），然後取每個字符串的第一個ñ字符小號並加入他們的轉化表示，XOR總對0x3,...，看看它的計算結果爲零。

爲了更快速地遍歷比O(n)，使用它來形成二叉搜索樹或堆（O(lg n) fetch）或散列（O(1) fetch）。如果S保證排序，這變得更加容易。

至少，如果我正確理解你的問題。爲了更好，更有理論的結果，有限的數學複雜性和證明，Math.SE或CSTheory.SE是前往位置。

來源

2012-03-31 00:02:00 MrGomez

那麼，這是回答一個問題不同於我回答。我不知道哪一個OP實際上意味着... – DRVic 2012-03-31 00:06:36

Decisionproblem上字符串

回答

相關問題