☰

查找具有非重复字符的最长子串的长度

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

在 shell（是的，可移植的）语言中，查找没有重复字符的最长子字符串（LSRC）非常简单sh（速度不快，shell 中的文本处理通常很慢）：

#!/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从（maketeststr和longestempty）中的整个输入字符串开始。然后，在一个循环中：
  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则不会删除任何内容；如果存在重复，则一步删除重复之前的所有字符。这是在 shell 中使用 完成的${frontstr#*"$c"}$c，只需一个变量扩展。

答案3

使用 POSIXsh参数扩展运算符，一次调用该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

使用 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)/
'

这给出了输入的每一行没有重复字符的最长字符序列，并假设输入不包含>字符。

相关内容