प्रश्न:

एक स्ट्रिंग S S.length() <= 5.10^5 और एक पूर्णांक K K <= S.length() दिया गया है। प्रत्येक निष्कासन के लिए, आप यह कर सकते हैं:

  • स्ट्रिंग का प्रथम वर्ण हटाएं
  • स्ट्रिंग का दूसरा वर्ण हटाएं
  • स्ट्रिंग का अंतिम वर्ण हटाएं
  • स्ट्रिंग का दूसरा अंतिम वर्ण हटाएं

मैं वास्तव में K निष्कासन कैसे कर सकता हूं जैसे कि अंतिम स्ट्रिंग में न्यूनतम शब्दावली क्रम हो?

उदाहरण:

एस = "अबकाबा", के = 2

  • स्ट्रिंग का दूसरा वर्ण हटाएं
  • स्ट्रिंग का दूसरा अंतिम वर्ण हटाएं

अंतिम स्ट्रिंग: "आकाआ" जो कि सबसे छोटी शब्दावली संभव है।

पी/एस:

मैंने कई दिनों तक कोशिश की है लेकिन इस समस्या को हल करने के लिए एक प्रभावशाली तरीका नहीं समझ सकता। लेकिन मुझे लगता है कि गतिशील प्रोग्रामिंग के साथ कुछ करना है।

6
unglinh279 20 अगस्त 2021, 07:47

5 जवाब

सबसे बढ़िया उत्तर

यहां पाइथन में एक (उम्मीद है) अधिकतर पूर्ण समाधान है (क्षमा करें, मैं सी ++ में भी कम जानता हूं)। विचार यह है कि मैं डेविड ईसेनस्टैट के समान या बहुत समान मानता हूं, जिनके जवाब ने मुझे मिडल को संभालने के बारे में और सोचने में मदद की। मध्य खंड के लिए तुलना ओ (1) लुकअप के साथ ओ (एन लॉग एन) प्रीप्रोसेसिंग के साथ प्रत्यय सरणी निर्माण के आधार पर संदर्भित और कोड में लिंक किया गया है (डेविड का सुझाव ओ (एन) प्रीप्रोसेसिंग और ओ (1) लुकअप का उपयोग करना है लेकिन मेरे पास ओ (1) आरएमक्यू या उकोनेन में आने का समय नहीं है; मैं संदर्भित सीपी प्रत्यय सरणी एल्गोरिदम से भी प्रभावित हूं)। कोड में ब्रूट-फोर्स की तुलना में परीक्षण शामिल है, लेकिन यह अधूरा है कि यह उस मामले को नहीं संभालता है जहां केवल उपसर्ग और प्रत्यय हैं और कोई मध्य नहीं है, जिसे वैसे भी संभालना बहुत आसान होना चाहिए। कोड को अधिक संक्षिप्त और व्यवस्थित बनाने के शायद तरीके हैं लेकिन मेरे पास अभी तक इस पर अधिक ध्यान से विचार करने का समय नहीं है।

चूंकि हम पहले, दूसरे, अंतिम या अंतिम वर्णों को हटा सकते हैं; समाधान के पहले दो अक्षर k या उससे कम हटाने के बाद शेष दो अक्षरों (एक अनुवर्ती) में से चुने जाएंगे:

xxxAxxxxxxxB...

एक बार जब हम कुछ पहले वर्णों को हटाकर वर्ण A के लिए प्रतिबद्ध हो जाते हैं, तो हमारे पास केवल B के लिए एक विकल्प रह जाता है, इस आधार पर कि हम दूसरे वर्ण से कितने विलोपन करते हैं। स्पष्ट रूप से, हम ए के लिए सबसे कम उपलब्ध कैरेक्टर चाहते हैं, जिसके हमारे पास एक से अधिक इंस्टेंस हो सकते हैं, और उसके बाद बी के लिए सबसे कम विकल्प, जिसके लिए हमारे पास एक से अधिक इंस्टेंस भी हो सकते हैं।

प्रत्यय समान रूप से बना है, लेकिन हमें उपसर्ग के लिए पहले से चुने गए प्रत्येक k - num_deletions के लिए सबसे अच्छा प्रत्यय संग्रहीत करने की आवश्यकता है। फिर अंतिम उम्मीदवार सबसे कम दो-वर्ण-उपसर्ग + मध्य + दो-वर्ण-प्रत्यय होता है, जहां प्रत्येक उम्मीदवार में विलोपन के वितरण द्वारा मध्य तय किया जाता है। हम अतिरिक्त जानकारी के साथ प्रत्यय सरणी या पेड़ का उपयोग करके मध्य की तुलना कर सकते हैं।

अजगर

def log2(n):
  i = -1
  while(n):
    i += 1
    n >>= 1
  return i

# https://cp-algorithms.com/string/suffix-array.html
def sort_cyclic_shifts(s):
  n = len(s)
  alphabet = 256
  cs = []

  p = [0] * n
  c = [0] * n
  cnt = [0] * max(alphabet, n)

  for i in range(n):
    cnt[ord(s[i])] += 1
  for i in range(1, alphabet):
    cnt[i] += cnt[i-1]
  for i in range(n):
    cnt[ord(s[i])] -= 1
    p[cnt[ord(s[i])]] = i
  c[p[0]] = 0
  classes = 1
  for i in range(1, n):
    if s[p[i]] != s[p[i-1]]:
      classes += 1
    c[p[i]] = classes - 1

  cs.append(c[:])

  pn = [0] * n
  cn = [0] * n
  h = 0

  while (1 << h) < n:
    for i in range(n):
      pn[i] = p[i] - (1 << h)
      if pn[i] < 0:
        pn[i] += n
      
    for i in range(0, classes):
      cnt[i] = 0

    for i in range(n):
      cnt[c[pn[i]]] += 1
    for i in range(1, classes):
      cnt[i] += cnt[i-1]
    for i in range(n-1, -1, -1):
      cnt[c[pn[i]]] -= 1
      p[cnt[c[pn[i]]]] = pn[i]
    cn[p[0]] = 0
    classes = 1
    for i in range(i, n):
      cur = c[p[i]], c[(p[i] + (1 << h)) % n]
      prev = c[p[i-1]], c[(p[i-1] + (1 << h)) % n]
      if cur != prev:
        classes += 1
      cn[p[i]] = classes - 1
    c = cn
    cs.append(c[:])
    h += 1

  return p, cs

# https://cp-algorithms.com/string/suffix-array.html
def suffix_array_construction(s):
  s += "$"
  sorted_shifts, cs = sort_cyclic_shifts(s)
  return sorted_shifts[1:], cs

# https://cp-algorithms.com/string/suffix-array.html
def compare(i, j, l, k, n, c):
  a = c[k][i], c[k][(i+l-(1 << k))%n]
  b = c[k][j], c[k][(j+l-(1 << k))%n]
  if a == b:
    return 0
  elif a < b:
    return -1
  return 1


## MAIN FUNCTION


def f(s, k):
  debug = 0

  n = len(s)

  # Best prefix
  best_first = s[k]
  best_second = s[k+1]
  first_idxs = [k]
  second_idxs = [k + 1]

  for i in range(k - 1, -1, -1):
    if s[i] <= best_first:
      best_first = s[i]
      # We only need one leftmost index
      first_idxs = [i]
  for i in range(k, first_idxs[0], -1):
    if (s[i] < best_second):
      best_second = s[i]
      second_idxs = [i]
    elif s[i] == best_second:
      second_idxs.append(i)

  second_idxs = list(reversed(second_idxs))

  # Best suffix
  # For each of l deletions,
  # we can place the last
  # character anywhere ahead
  # of the penultimate.
  last_idxs = {(n - 2): [n - 1]}
  best_last = s[n - 1]
  for l in range(2, k + 2):
    idx = n - l
    if s[idx] < best_last:
      best_last = s[idx]
      last_idxs[n - 1 - l] = [idx]
    else:
      last_idxs[n - 1 - l] = last_idxs[n - l]

  p, cs = suffix_array_construction(s)

  second_idx = 0

  if debug:
    print(first_idxs, second_idxs, last_idxs)

  while first_idxs[0] >= second_idxs[second_idx]:
    second_idx += 1

  prefix_end = second_idxs[second_idx]
  num_deleted = prefix_end - 1
  remaining = k - num_deleted
  suffix_start = n - remaining - 2
  best = (prefix_end + 1, suffix_start - 1)

  while second_idx < len(second_idxs):
    prefix_end = second_idxs[second_idx]
    num_deleted = prefix_end - 1
    remaining = k - num_deleted
    suffix_start = n - remaining - 2

    len_candidate_middle = suffix_start - 1 - prefix_end

    # The prefixes are all equal.
    # We need to compare the middle
    # and suffix.
    # compare(i, j, l, k, n, c)
    len_best_middle = best[1] - best[0] + 1
    l = min(len_candidate_middle, len_best_middle)

    # Compare middles
    comp = compare(best[0], prefix_end + 1, l, log2(l), n + 1, cs)

    # Candidate is better
    if comp == 1:
      best = (prefix_end + 1, suffix_start - 1)
    elif comp == 0:
      # Compare suffix of candidate with
      # substring at the comparable position
      # of best.
      [last_idx] = last_idxs[suffix_start]
      candidate_suffix = s[suffix_start] + s[last_idx]

      if len_candidate_middle < len_best_middle:
        # One character of best's suffix
        if len_candidate_middle + 1 == len_best_middle:
          to_compare = s[best[1]] + s[best[1] + 1]
        # None of best's suffix
        else:
          idx = best[0] + len_candidate_middle
          to_compare = s[idx] + s[idx + 1]
        # If the candidate suffix is equal
        # to best's equivalent, the candidate
        # wins since it's shorter.
        if candidate_suffix <= to_compare:
          best = (prefix_end + 1, suffix_start - 1)

      elif len_candidate_middle == len_best_middle:
        idx = best[1] + 1
        to_compare = s[idx] + s[last_idxs[idx][0]]
        if candidate_suffix < to_compare:
          best = (prefix_end + 1, suffix_start - 1)

      # len_best_middle < len_candidate_middle 
      else:
        # One character of candidate's suffix
        if len_best_middle + 1 == len_candidate_middle:
          to_compare = s[suffix_start - 1] + s[suffix_start]
        # None of candidates's suffix
        else:
          idx = prefix_end + 1 + len_best_middle
          to_compare = s[idx] + s[idx + 1]

        if candidate_suffix < to_compare:
          best = (prefix_end + 1, suffix_start - 1)

    second_idx += 1

  prefix = s[first_idxs[0]] + s[second_idxs[second_idx-1]]
  middle = s[best[0]:best[1] + 1]
  suffix = s[best[1] + 1] + s[last_idxs[best[1] + 1][0]]

  return prefix + middle + suffix


def brute_force(s, k):
  best = s + "z"
  stack = [(s, k)]

  while stack:
    _s, _k = stack.pop()
    if _k == 0:
      best = min(best, _s)
      continue
    stack.append((_s[1:], _k - 1))
    stack.append((_s[0] + _s[2:], _k - 1))
    stack.append((_s[0:len(_s)-1], _k - 1))
    stack.append((_s[0:len(_s)-2] + _s[-1], _k - 1))

  return best

#    01234567
#s = "abacaaba"
#k = 2

# Test
import random

n = 12
num_tests = 500

for _ in range(num_tests):
  s = "".join([chr(97 + random.randint(0, 25)) for i in range(n)])
  k = random.randint(1, n - 5)
  #print(s, k)
  _f = f(s, k)
  brute = brute_force(s, k)
  if brute != _f:
    print("MISMATCH!")
    print(s, k)
    print(_f)
    print(brute)
    break

print("Done.")
2
גלעד ברקן 2 सितंबर 2021, 10:42

सभी एक साथ, इन विचारों को एक रैखिक-समय एल्गोरिथ्म की ओर ले जाना चाहिए।

यदि K N−4, अंतिम स्ट्रिंग में कम से कम चार वर्ण हैं। इसका दो-वर्ण उपसर्ग प्रारंभिक स्ट्रिंग के (K+2)-वर्ण उपसर्ग के कम से कम दो-वर्णों के बाद है। इस उपसर्ग और इसके दूसरे वर्ण की संभावित स्थितियों की गणना करें। यह O(K) समय में पहले K+2 वर्णों के माध्यम से स्कैन करके, अब तक के सबसे कम वर्ण और अब तक के कम से कम दो-वर्णों के बाद को बनाए रखते हुए पूरा किया जा सकता है।

अब जबकि हम द्वि-वर्ण उपसर्ग को जानते हैं, हमें केवल सर्वोत्तम प्रत्यय का निर्धारण करना है। एक उपसर्ग के लिए जिसे सेट करने के लिए J विलोपन की आवश्यकता होती है, अंतिम स्ट्रिंग अगले N−4 - K वर्णों के साथ जारी रहती है जिन्हें हम स्पर्श नहीं कर सकते हैं, इसके बाद (K+2 - J) -चरित्र के कम से कम दो-वर्णों के बाद प्रारंभिक स्ट्रिंग का प्रत्यय। हम पहले वर्णित स्कैनिंग एल्गोरिदम का उपयोग करके प्रत्येक प्रासंगिक प्रत्यय के कम से कम दो-वर्णों के बाद की गणना कर सकते हैं। एक मुश्किल हिस्सा अछूत मध्यस्थों की कुशलता से तुलना करना है। यह सबसे लंबे समय तक सामान्य उपसर्गों के साथ प्रत्यय सरणी का उपयोग करके कुछ कठिनाई के साथ पूरा किया जा सकता है।

यदि K > N−4, बस कम से कम (N−K) -चरित्र क्रमानुसार लौटाएं।

4
David Eisenstat 20 अगस्त 2021, 17:41

दिलचस्प काम!

अद्यतन: चरण 5 गलत। यहाँ एक सही है:

लंबाई M के साथ सभी संयोजन, जिसमें 3' और 4' के निष्कासन ऑपरेशन शामिल हैं, इस वर्ग के संचालन के बराबर हैं: शून्य या अधिक 3 उसके बाद शून्य या अधिक 4, जैसे यह regexp: (3)(4) आप इसे साबित कर सकते हैं:

  1. 43 जोड़ी 33 . के बराबर है
  2. 343 जोड़ी 443 के बराबर।
  3. इसके अलावा 34...43 44...43 के बराबर है।

तो आप सबसे दाहिने 3 को चुन सकते हैं और नियम 3 के साथ इसे केवल एक ही बना सकते हैं। और नियम 4 के साथ सभी बाएँ 4 को 3 में बदल दें।

कोई भी ->नियम3->4...434...4 ->नियम1->3...34...4

यह चरण 6 पाशविक बल की O(K^3) जटिलता की ओर ले जाता है।


मूल उत्तर

कुछ विचार और समाधान हैं जो सामान्य रूप से अच्छा काम करते हैं

  1. [शब्दकोश के क्रम में अधिक छोटा शब्द छोटा है] गलत, @n के रूप में। 1.8e9-कहां-मेरा-शेयर एम। मनोनीत। सभी संभावित परिणाम समान लंबाई (Length-K) के होंगे, क्योंकि हमें उन सभी का उपयोग करना चाहिए।
  2. लेक्सिकोग्राफिकल ऑर्डर का अर्थ है: अर्ध-लंबाई वाले शब्दों के लिए हम प्रतीकों को बाएं से दाएं तब तक मिलाते हैं जब तक कि यह बराबर न हो जाए। शब्द तुलना का परिणाम पहले अलग चार तुलना परिणाम का परिणाम है। इसलिए सभी सकारात्मक j के लिए i'th प्रतीक को छोटा करना (i+j) वें प्रतीक को छोटा करने से अधिक महत्वपूर्ण है।
  3. तो सबसे महत्वपूर्ण पहला प्रतीक न्यूनीकरण है। केवल पहला निष्कासन ऑपरेशन ही उस पर प्रभाव डाल सकता है। पहले निष्कासन ऑपरेशन द्वारा हम पहले स्थान पर न्यूनतम संभव मान रखने का प्रयास करते हैं (यह पहले K प्रतीकों से न्यूनतम मान होगा)। यदि न्यूनतम अक्षर के साथ कुछ स्थान हैं - हम सबसे बाईं ओर वाले को चुनेंगे (हम अतिरिक्त प्रतीकों को हटाना नहीं चाहते हैं और सही उत्तर खो गए हैं)।
  4. अब सबसे महत्वपूर्ण दूसरा अक्षर है। इसलिए हम इसे भी कम करना चाहते हैं। हम इसे एल्गोरिथम के 3'वें चरण की तरह बना देंगे। लेकिन, हम 2'nd remove ऑपरेशन का उपयोग करते हैं और यदि हमारे पास कुछ प्रकार न्यूनतम हैं - तो हम उन सभी को उम्मीदवारों के रूप में सहेजते हैं।
  5. M लंबाई वाले सभी संयोजन, जिनमें 3'वें और 4'वें हटाने के ऑपरेशन शामिल हैं, केवल 2 संयोजनों के बराबर हैं:
  • सभी ऑपरेशन 4'वें हैं: 44...44
  • सभी ऑपरेशन 4'वें हैं लेकिन आखिरी वाला 3:44...43 है। इसलिए प्रत्येक उम्मीदवार के लिए हम केवल दो संभावनाओं की जांच कर सकते हैं।
  1. दोनों संभावनाओं के साथ सभी उम्मीदवारों पर बल दें। न्यूनतम खोजें।

सामान्य स्थिति में यह एल्गोरिथम अच्छी तरह से काम करता है। लेकिन सबसे खराब स्थिति में यह कमजोर है। काउंटरपॉइंट है: एक ही अक्षर के साथ मैक्सलेंथ स्ट्रिंग। फिर हमारे पास K उम्मीदवार हैं और एल्गोरिथम जटिलता O(K^2) होगी - यह इस कार्य के लिए अच्छा नहीं है।

इससे निपटने के लिए मुझे लगता है कि हम एल्गोरिथम के 6वें चरण में सही उम्मीदवार चुन सकते हैं:

6*. दो उम्मीदवारों के लिए - उसके बाद उनके प्रत्यय - अक्षरों की तुलना करें। एक ही पूंछ की स्थिति में छोटे अक्षर वाले उम्मीदवार (इस उम्मीदवार के सिर की स्थिति से पूंछ की स्थिति की गणना) हमारे उद्देश्यों के लिए बेहतर है।

7*. 5वें एल्गोरिथम चरण के रूप में दो संभावनाओं की तुलना करें और न्यूनतम चुनें।

इस (*) दृष्टिकोण की समस्या - मुझे एक कठोर प्रमाण नहीं मिल सकता है कि यह बेहतर समाधान है। सबसे कठिन हिस्सा, जब एक उम्मीदवार दूसरे का उपसर्ग होता है - हम अक्षर से अक्षर की तुलना तब तक करते हैं जब तक कि सबसे छोटा समाप्त न हो जाए। उदाहरण के लिए पहले और चौथे स्थान पर उम्मीदवार के साथ स्ट्रिंग abcabcabc...abc में।

3
Nikxp 20 अगस्त 2021, 13:00

Abcbaa के लिए एक गैर-समाधान विफल, K = 2
(एक परीक्षण साझा करने के लिए बधाई।)

  • पहले K +1 तत्वों में न्यूनतम 0-आधारित अनुक्रमणिका l1 पर खोजें
  • लंबाई का उपसर्ग छोड़ दें l1 (पहली l1 बार निकालें) - अगर l1 = K
  • 1 से 1 + K - l1 तक के तत्वों में न्यूनतम खोजें, जिसमें l2 शामिल हैं
  • तत्वों को 1 से l2 तक "हटाएं" (यदि कोई हो)(दूसरी l2 बार निकालें)
  • l3 = 0 से शुरू होता है और जबकि K - l1 - l2 - l3 > 0,
    पिछले दो तत्वों में से बड़ा तत्व निकालें और l3 . बढ़ाएं
1
3 revs 2 सितंबर 2021, 06:12

मैं इस उत्तर को पोस्ट करूंगा, भले ही एक स्वीकृत उत्तर हो क्योंकि मुझे ऐसा लगता है कि अन्य सभी उत्तर उनकी आवश्यकता से अधिक जटिल हैं। नीचे एक ओ (एनके) एल्गोरिदम है जो इसे हल करता है, जिसे "आसानी से" ओ (एन) एल्गोरिदम में बनाया जा सकता है यदि "मध्य" भागों की तुलना करने के लिए प्रत्यय पेड़ का उपयोग किया जाता है।

#!/usr/bin/python

def lex_kr(x,K,k_r):
    """
    Get a lexicographically comparable subset of `x` for a given value of
    `k_r`.
    """
    N = len(x)
    assert k_r > 0 and k_r < K # check for corner cases
    k_l = K - k_r
    v_l = min(x[:k_l])
    v_r = min(x[-k_r:])

    lex = [v_l]
    lex += x[k_l+1:N-k_r-1]
    lex += [v_r]

    return lex

def lex_corner(x,K):
    """
    Get the two lexicographically comparable subsets of `x` for corner cases
    when `k_r=0` and `k_r=K`.
    """
    N = len(x)

    k_l = K
    v_l = min(x[:k_l])
    lex0 = [v_l]
    lex0 += x[k_l+1:]

    k_r = K
    v_r = min(x[-k_r:])
    lex1 = x[:N-k_r-1]
    lex1 += [v_r]

    return lex0,lex1


def min_lex(x,K):
    subsets = [ lex_kr(x,K,k_r) for k_r in range(1,K) ]
    subsets += lex_corner(x,K) # append the two corner cases
    return min(subsets)

if __name__ == '__main__':

    S = [ x for x in 'abacaaba' ]
    K = 2

    print(min_lex(S,K))

जो ['a', 'a', 'c', 'a', 'a', 'a'] प्रिंट करता है।

सरणियों के बाएँ और दाएँ (उपसर्ग और प्रत्यय) के min की तुलना स्पष्ट रूप से फ़ंक्शन lex_kr में O(N) समय में पूर्व-गणना की जा सकती है।

मध्य भाग (अर्थात x[k_l+1:N-k_r-1]) को अन्य सभी मध्य भागों के साथ कुशलतापूर्वक तुलना करने के लिए एक चतुर चाल की आवश्यकता है। यह अन्य उत्तरों में वर्णित प्रत्यय-पेड़/सरणी का उपयोग करके O(1) प्रति तुलना में किया जा सकता है (https://cp-algorithms.com/string/suffix-array.html) या एक प्रत्यय automaton (https://cp-algorithms.com/string/suffix-automaton.html) बाद वाला अधिक जटिल लेकिन अधिक कुशल होने के साथ। एक बार लागू होने के बाद, यह अन्य उत्तरों की तुलना में कम विशेष मामलों के साथ ओ (एन) एल्गोरिदम उत्पन्न करेगा।

1
ldog 2 सितंबर 2021, 20:22