☰

繰り返されない文字を含む最も長い部分文字列の長さを見つけます。

tag-icon • tag-icon bash text-processing
繰り返されない文字を含む最も長い部分文字列の長さを見つけます。

文字を繰り返さずにその部分文字列の長さを返さずに、最も長い部分文字列を探しています。

たとえば、次の入力が与えられた場合：

abcbdbdsdfng

出力は次のようになります。

5

説明する：

  • 最初の文字列はabc（長さ3）です。
  • 次の可能性はcbd（長さ3）です。
  • 次の可能性はdb（長さ2）です。
  • 次の可能性はbds（長さ3）です。
  • 次の可能性はsdfng（長さ5）です。

したがって、この例にはsdfng一意の文字のみを含む最も長い部分文字列があります。

答え1

POSIXsh構文を使用し、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.

説明のための2つの一般的なアルゴリズムがあります。繰り返される文字を持たない最も長い部分文字列を見つける

「スライディングウィンドウ」方法としても知られている2番目の方法は、次のように機能します。

  1. str（maketeststrと空）longestの完全な入力文字列で始まります。次に、ループで次のことを行います。
  2. cの先頭から文字（）を抽出しますstr。
  3. c重複がないか確認してくださいteststr。
  4. 繰り返す場合は、c前の文字を削除してくださいteststr。
  5. c繰り返されない項目が1つありますteststr。cに追加してくださいteststr。
  6. teststrより長いことを確認してくださいlongest。もしそうなら、文字列をlongest。
  7. これ以上文字がないと、strループは終了します。

ステップ3、4、5は次のように単純化できます。一つ文字列操作：「c存在する場合はすべて削除して追加しますc」。重複がなければcurrChar何も削除されず、重複があると重複する前のすべての文字が一度に削除されます。これは${frontstr#*"$c"}$c1つの変数拡張を使用してシェルで行われます。

答え3

POSIXsh引数拡散演算子を使用してprintfユーティリティを1回呼び出し、複数回呼び出します[。

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

POSIXsh構文とユーティリティへの単一の呼び出しを使用して、次のことを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)/
'

これは、入力に文字がないと仮定すると、入力の各行に対して繰り返される文字を持たない最も長い文字シーケンスを提供します>。

関連情報