☰

반복되지 않는 문자가 포함된 가장 긴 부분 문자열의 길이를 찾습니다.

tag-icon • tag-icon bash text-processing
반복되지 않는 문자가 포함된 가장 긴 부분 문자열의 길이를 찾습니다.

문자를 반복하지 않고 해당 하위 문자열의 길이를 반환하지 않고 가장 긴 하위 문자열을 찾고 있습니다.

예를 들어, 다음 입력이 주어지면:

abcbdbdsdfng

출력은 다음과 같아야 합니다.

5

설명하다:

  • 첫 번째 문자열은 abc(길이 3) 입니다.
  • 다음 가능성은 cbd(길이 3) 입니다.
  • 다음 가능성은 db(길이 2) 입니다.
  • 다음 가능성은 bds(길이 3) 입니다.
  • 다음 가능성은 sdfng(길이 5) 입니다.

따라서 이 예에는 sdfng고유 문자만 포함하는 가장 긴 하위 문자열이 있습니다.

답변1

POSIX sh구문을 사용하고 awk유틸리티를 한 번 호출하십시오.

<input awk '
  {
    cur = longest = ""
    n = l = 0
    while ($0 != "") {
      c = substr($0, 1, 1)
      if (i = index(cur, c)) {
        cur = substr(cur, i+1)
        l -= i
      }
      $0 = substr($0, 2)
      cur = cur c
      if (++l > n) {
        n = l
        longest = cur
      }
    }
    printf "\"%s\" (%d)\n", longest, n
  }'

답변2

셸(예, 이식 가능) 언어에서는 반복 문자가 없는 가장 긴 부분 문자열(LSRC)을 찾는 것이 매우 간단합니다 sh(빠르지 않으며 셸의 텍스트 처리가 일반적으로 느립니다).

#!/bin/sh

str=$1  longest='' teststr=''

while [ "${str}" ]; do
    c=${str%"${str#?}"}              # extract one char to test it.

    str=${str#?}                     # remove the character from str.

    teststr=${teststr#*"$c"}$c       # Build teststr by appending $c
                                     # remove leading repeated char.

              l1=${#longest}         # length of longest found
              l2=${#teststr}         # length of tested string

    if     [ "$l1" -lt "$l2" ]       # if tested is longer than longest
    then   longest=$teststr          # store it in longest.
    fi

done

echo "$longest ${#longest}";         # print longest found and length.

설명을 위한 두 가지 일반적인 알고리즘이 있습니다.반복되는 문자가 없는 가장 긴 부분 문자열 찾기

"슬라이딩 윈도우" 방법으로도 알려진 두 번째 방법은 다음과 같이 작동합니다.

  1. str(make teststr및 비어 있음) longest의 전체 입력 문자열로 시작합니다 . 그런 다음 루프에서 다음을 수행합니다.
  2. c의 앞부분에서 문자( )를 추출합니다 str.
  3. c중복이 있는지 확인하세요 teststr.
  4. 반복 되면 c계속해서 이전 문자를 삭제하세요 teststr.
  5. c반복되지 않는 항목 이 하나 있습니다 teststr. c에 추가하세요 teststr.
  6. teststr보다 긴지 확인하세요 longest. 그렇다면 문자열을 longest.
  7. 더 이상 문자가 없으면 str루프가 종료됩니다 .

3, 4, 5단계는 다음과 같이 단순화될 수 있습니다.하나문자열 작업: " c있는 경우 모두 제거하고 추가합니다 c". 중복이 없으면 currChar아무것도 삭제되지 않으며, 중복이 있으면 중복 이전의 모든 문자가 한 번에 삭제됩니다. 이는 ${frontstr#*"$c"}$c하나의 변수 확장을 사용하여 셸에서 수행됩니다 .

답변3

POSIX sh인수 확산 연산자를 사용하여 printf유틸리티를 한 번 호출하고 여러 번 호출합니다 [.

string=abcbdbdsdfng

cur= n=0 longest=
while [ -n "$string" ]; do
  c=${string%"${string#?}"}

  new_cur=${cur#*"$c"}
  if [ "$new_cur" = "$cur" ]; then
    cur=$cur$c
    string=${string#?}
    l=${#cur}
    if [ "$l" -gt "$n" ]; then
      n=$l longest=$cur
    fi
  else
    cur=$new_cur
  fi
done
printf '"%s" (%d)\n' "$longest" "$n"

답변4

POSIX sh구문과 유틸리티에 대한 단일 호출을 사용하여 sed다음을 수행할 수 있습니다.

<input sed '
  # clean-up hold space
  x;s/.*//;x

  # insert a running ">" cursor
  s/^/>/
  :start
  />$/! {
    # pull the next character
    s/>\(.\)/\1>/

    # if what is left of > contains a duplicated character
    /\(.\).*\1.*>/ {
      # remove first char
      s/^.//
      b start
    }

    # does not contain a duplicated char. Is it longer than
    # the currently selected one?

    H; # append to hold space
    g;s/\n/>/;s/[^>]/./g
    # now the pattern space contains ...>....>... and we compare
    # the number of .s in the first two sections

    /^\([^>]*\)>\1[^>]/ {
      # it is longer, store in hold space
      g
      s/.*\n//;s/>.*//
      x
      s/.*\n//
      b start
    }

    # it is not longer
    g
    s/\n.*//;x;s/.*\n//
    b start
  }
  g

  # count the number of characters
  s/./o/g
  s/^/:|/
  :1
  s/|o\{10\}/x|/
  t 1

  s/$/9876543210/
  s/\(.*:\)\(x*\)|.\{9\}\(.\).*/\3\1|\2/
  y/x/o/
  /o/b1
  s/:.*//
  G
  s/\(.*\)\n\(.*\)/"\2" (\1)/
'

이는 입력에 문자가 없다고 가정할 때 입력의 각 줄에 대해 반복되는 문자가 없는 가장 긴 문자 시퀀스를 제공합니다 >.

관련 정보