10

（感谢下面的 greg0ire 对关键概念的帮助）

挑战：构建一个程序来查找所有子字符串并用颜色属性“标记”它们（有效地在 XML 中突出显示它们）。

规则：

  1. 这只应该对长度为 2 或更长的子字符串进行。
  2. 子字符串只是连续字符的字符串，其中可能包括非字母字符。请注意，空格和其他标点符号不会分隔子字符串。
  3. 字符大小写不能忽略。
  4. “突出显示”应该通过在 XML 中标记子字符串来完成。您的标记应采用该子字符串和相同子字符串唯一的正数的<TAG#>theSubstring</TAG#>形式#。
  5. 该算法的优先级是找到最长的子字符串，而不是在文本中匹配多少次。

注意：下面示例中显示的标记顺序并不重要。为了清楚起见，它只是由 OP 使用。

示例输入：

LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s,whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook.

部分正确的输出（在此示例中，OP 可能没有完全替换）

<TAG1>LoremIpsum</TAG1>issimply<TAG2>dummytext</TAG2>of<TAG5>the</TAG5><TAG3>print</TAG3>ingand<TAG4>type</TAG4>setting<TAG6>industry</TAG6>.<TAG1>LoremIpsum</TAG1>hasbeen<TAG5>the</TAG5><TAG6>industry</TAG6>'sstandard<TAG2>dummytext</TAG2>eversince<TAG5>the</TAG5>1500s,whenanunknown<TAG3>print</TAG3>ertookagalleyof<TAG4>type</TAG4>andscrambledittomakea<TAG4>type</TAG4>specimenbook.

您的代码应该能够处理边缘情况，例如：

示例输入 2：

hello!TAG!</hello.TAG.</

示例输出 2：

<TAG1>hello</TAG1>!<TAG2>TAG</TAG2>!<TAG3></</TAG3><TAG1>hello</TAG1>.<TAG2>TAG</TAG2>.<TAG3></</TAG3>

获胜者，冠军：

  • 最优雅的解决方案获胜（根据其他评论、赞成票来判断）
  • 使用 shell 脚本的解决方案的奖励积分/注意事项

小说明：

  • 输入可以硬编码或从文件中读取
  • 标准仍然是“优雅”，诚然有点模糊，但它也封装了简单的字符/行数。其他人的评论和/或赞成票也表明 SO 社区如何看待挑战
4

7 回答 7

4

Perl206,189,188,199, 157 个字符

不包括原始字符串和最后一次打印。

 #New algorithm that produces correct ouputs for many cases



    push@z,q/LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s,whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook/;

    push@z,q/oktooktobookokm/;
    push@z,q!dino1</dino2</!;
    push@z,q!dino1TAG2dino3TAG!;

    ## loop for tests doesn't count
    for $z(@z) {
    print "input : $z\n";
    $i=0;@r=();
    #### begin count
    $c=127;$l=length($_=$z);while($l>1){if(/(.{$l}).*\1/){push@r,$1;++$c;s/$1/chr($c)/eg}else{$l--}}$z=$_;map{++$i;$x=chr(127+$i);$z=~s:$x:<TAG$i>$_</TAG$i>:g}@r
    #### end count 157 chars
    ## output doesn't count
    ;print "output : $z\n","="x80,"\n"
    }

__END__
perl tags2.pl
input : LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe15
00s,whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook

output : <TAG1>LoremIpsum</TAG1>i<TAG11>ss</TAG11><TAG12>im</TAG12>ply<TAG2>dummytext</TAG2><TAG6>oft</TAG6><TAG13>he</TAG13><TAG4>p
rint</TAG4><TAG7>ing</TAG7><TAG8>and</TAG8><TAG5>types</TAG5>e<TAG14>tt</TAG14><TAG7>ing</TAG7><TAG3>industry</TAG3>.<TAG1>LoremIpsu
m</TAG1>hasbe<TAG15>en</TAG15><TAG9>the</TAG9><TAG3>industry</TAG3>'<TAG11>ss</TAG11>t<TAG8>and</TAG8>ard<TAG2>dummytext</TAG2>ev<TA
G16>er</TAG16>since<TAG9>the</TAG9>1500s,w<TAG13>he</TAG13>nanunknown<TAG4>print</TAG4><TAG16>er</TAG16>t<TAG10>ook</TAG10>agal<TAG1
7>le</TAG17>y<TAG6>oft</TAG6>y<TAG18>pe</TAG18><TAG8>and</TAG8>scramb<TAG17>le</TAG17>di<TAG14>tt</TAG14>omakea<TAG5>types</TAG5><TA
G18>pe</TAG18>c<TAG12>im</TAG12><TAG15>en</TAG15>b<TAG10>ook</TAG10>
================================================================================
input : oktooktobookokm
output : <TAG1>okto</TAG1><TAG1>okto</TAG1>bo<TAG2>ok</TAG2><TAG2>ok</TAG2>m
================================================================================
input : dino1</dino2</
output : <TAG1>dino</TAG1>1<TAG2></</TAG2><TAG1>dino</TAG1>2<TAG2></</TAG2>
================================================================================
input : dino1TAG2dino3TAG
output : <TAG1>dino</TAG1>1<TAG2>TAG</TAG2>2<TAG1>dino</TAG1>3<TAG2>TAG</TAG2>
================================================================================
于 2010-07-06T12:52:25.733 回答
2

Python，236 206 个字符

s="LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s,whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook."
### ------------------------------------------------------------
import re
c=o=127
l={}
i=len(s)/2
while i>1:
    r=re.search('(.{%d}).*\\1'%i,s)
    if r:f=r.group(1);c+=1;l[c-o]=f;s=s.replace(f,chr(c))
    else:i-=1
for i in l:s=re.sub(chr(i+o),'<TAG%d>%s</TAG%d>'%(i,l[i],i),s)
### ------------------------------------------------------------
print s

在示例输入上运行它的结果，它选择以下单词 （'LoremIpsum'、'dummytext'、'industry'、'print'、'types'、'oft'、'ing'、'and'、' the', 'ook', 'ss', 'im', 'he', 'tt', 'en', 'er', 'le', 'pe')结果是：

<TAG1>LoremIpsum</TAG1>i<TAG11>ss</TAG11><TAG12>im</TAG12>ply<TAG2>dummytext</TAG2><TAG6>oft</TAG6><TAG13>he</TAG13><TAG4>print</TAG4><TAG7>ing</TAG7><TAG8>and</TAG8><TAG5>types</TAG5>e<TAG14>tt</TAG14><TAG7>ing</TAG7><TAG3>industry</TAG3>.<TAG1>LoremIpsum</TAG1>hasbe<TAG15>en</TAG15><TAG9>the</TAG9><TAG3>industry</TAG3>'<TAG11>ss</TAG11>t<TAG8>and</TAG8>ard<TAG2>dummytext</TAG2>ev<TAG16>er</TAG16>since<TAG9>the</TAG9>1500s,w<TAG13>he</TAG13>nanunknown<TAG4>print</TAG4><TAG16>er</TAG16>t<TAG10>ook</TAG10>agal<TAG17>le</TAG17>y<TAG6>oft</TAG6>y<TAG18>pe</TAG18><TAG8>and</TAG8>scramb<TAG17>le</TAG17>di<TAG14>tt</TAG14>omakea<TAG5>types</TAG5><TAG18>pe</TAG18>c<TAG12>im</TAG12><TAG15>en</TAG15>b<TAG10>ook</TAG10>.

在这个 wiki 上哪个更易读，像这样突出显示：

LoremIpsum我ssim玩。dummytextoftheprintingandtypes_ 自从1500 年代以来一直是t ard ev ，w nanunknown t agal y y scramb di omakea c b 。ttingindustryLoremIpsumentheindustryssanddummytextertheheprinterookleoftpeandletttypespeimenook

PS。有人抱怨，所以我添加了输入和输出语句。我向困惑的人道歉——这对我来说似乎很明显。显然不是，所以我添加了前缀/预告片语句，这些语句不是问题规范所要求的，不应计入代码长度。

于 2010-07-07T05:44:21.860 回答
1

Haskell：343/344 403 420 445 485个字符

使用指数算法时字符数为 343，而使用二次算法时字符数为 344。

发布的代码是二次代码。对于指数算法，将代码中出现的一次更改为inits=<<tailsto subsequences。

import Data.List
l=length
e=map$either id id
(&)=stripPrefix
y@(_:w)!x=l x>1&&maybe(w!x)(isInfixOf x)(x&y)
_!_=0<0
t@(x,i)?s@(y:z)=maybe(y:t?z)(((map Right$'<':v++e x++"</"++v)++).(t?))$x&s where v="TAG"++i++">"
_?_=[]
r s=e$foldr(?)s$zip(sortBy(\a b->compare(l a)$l b)$filter(s!)$inits=<<tails s)$map show[1..]
main=getLine>>=putStr.r.map Left

输入 1：

LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s,whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook.

输出 1：

<TAG338>LoremIpsum</TAG338>i<TAG72>ss</TAG72><TAG122>im</TAG122>ply<TAG336>dummytext</TAG336><TAG188>oft</TAG188><TAG91>he</TAG91><TAG275>print</TAG275><TAG153>ing</TAG153><TAG191>and</TAG191><TAG276>types</TAG276><TAG88>et</TAG88><TAG214>ting</TAG214><TAG328>industry</TAG328>.<TAG338>LoremIpsum</TAG338>hasbe<TAG123>en</TAG123><TAG183>the</TAG183><TAG328>industry</TAG328>'s<TAG73>st</TAG73><TAG191>and</TAG191>ard<TAG336>dummytext</TAG336>ev<TAG99>er</TAG99>s<TAG96>in</TAG96>ce<TAG183>the</TAG183>1500s,wh<TAG123>en</TAG123><TAG111>an</TAG111>unknown<TAG275>print</TAG275><TAG99>er</TAG99>t<TAG195>ook</TAG195>a<TAG103>ga</TAG103>l<TAG113>le</TAG113>y<TAG105>of</TAG105><TAG241>type</TAG241><TAG191>and</TAG191>scramb<TAG113>le</TAG113>dit<TAG115>to</TAG115>mak<TAG116>ea</TAG116><TAG276>types</TAG276><TAG121>pe</TAG121>c<TAG122>im</TAG122><TAG123>en</TAG123>b<TAG195>ook</TAG195>.

输入 2：

hello!TAG!</hello.TAG.</

输出 2：

<TAG28>hello</TAG28>!<TAG22>TAG</TAG22>!<TAG14></</TAG14><TAG28>hello</TAG28>.<TAG22>TAG</TAG22>.<TAG14></</TAG14>
于 2010-07-06T18:25:11.263 回答
0

Python，236 281 个字符，没有正则表达式 :)

制作一组M所有 2+ 个字符串，然后遍历它们以按贪心长度顺序分配它们

s="LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s,whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook."
#s="abcd1TAGabcd2TAG"

### ----
L,C,R=len,chr,range
M,l,T,t=set(),L(s),[],0
[[M.add(s[A:B])for B in R(A+2,l)]for A in R(l)]
while 1:
 m,t=sorted([(L(m),m)if s.count(m)>1 else(0,"")for m in M])[-1][1],t+1
 if m=="":break
 T+=[(t,m)]
 s=s.replace(m,C(t))
for(t,m)in T:
 s=s.replace(C(t),"<TAG%d>%s</TAG%d>"%(t,m,t))
### ----

print s

输出，如预期：

<TAG1>LoremIpsum</TAG1>i<TAG11>ss</TAG11><TAG15>im</TAG15>ply<TAG2>dummytext</TAG2><TAG13>of</TAG13><TAG6>the</TAG6><TAG5>print</TAG5><TAG8>ing</TAG8><TAG9>and</TAG9><TAG4>types</TAG4>e<TAG10>tt</TAG10><TAG8>ing</TAG8><TAG3>industry</TAG3>.<TAG1>LoremIpsum</TAG1>hasbe<TAG17>en</TAG17><TAG6>the</TAG6><TAG3>industry</TAG3>'<TAG11>ss</TAG11>t<TAG9>and</TAG9>ard<TAG2>dummytext</TAG2>ev<TAG16>er</TAG16>since<TAG6>the</TAG6>1500s,wh<TAG17>en</TAG17>anunknown<TAG5>print</TAG5><TAG16>er</TAG16>t<TAG7>ook</TAG7>agal<TAG14>le</TAG14>y<TAG13>of</TAG13>ty<TAG12>pe</TAG12><TAG9>and</TAG9>scramb<TAG14>le</TAG14>di<TAG10>tt</TAG10>omakea<TAG4>types</TAG4><TAG12>pe</TAG12>c<TAG15>im</TAG15><TAG17>en</TAG17>b<TAG7>ook</TAG7>.
于 2010-07-07T22:07:34.263 回答
0

Mathematica - 262 个字符

不是纯粹的功能性/不短/不好/很多副作用/ 

b = "LoremIpsumissimplydummytextoftheprintingandtypesettingindustry.\
     LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s,\
     whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimen\
     book."

i = 0
a = c = "@"
v = StringFreeQ@## &
w = StringReplace@## &
t = x__ ~~ y__ ~~ __ ~~ x__ ~~ y__ /; v[x <> y, c]
NestWhile[
  w[#, (a = SortBy[StringCases[#, t -> x <> y,Overlaps -> True], -StringLength@# &][[1]]) -> c] &,
  b,
  (z = k@++i; b = w[b, a -> "<TAG" <> z <> ">" <> a <> "</TAG" <> z <> ">"] /. k -> IntegerString; True) && ! v[#, t] &]
于 2010-07-10T06:29:13.780 回答
0

我认为您可以使用反向引用来执行此操作。看到这篇文章：正则表达式检测字符串中的重复 我已经做了很多尝试，目前我有这个表达式：#([a-zA-Z]+).*\1#，但我认为它找到了第一个重复的字符串，不是最大的...... 这是在我知道你不在乎文字之前......你应该做的是：

  • 找到文本中重复的最大字符序列
  • 从它出现的文本中删除它
  • 迭代直到你发现没有重复
  • 使用 tomit 的方法为你记住的字符串着色

该步骤在此页面上进行了描述：http ://en.wikipedia.org/wiki/Longest_common_substring_problem 这是一个 php 实现：http ://www.davidtavarez.com/archives/longer-common-substring-problem-php- implementation/（你必须修复它，它包含 html 实体，并且注释说它返回一个整数但我们不知道它代表什么......），如果它仍然不起作用，你可以尝试实现维基百科的伪代码。

于 2010-07-03T13:29:36.217 回答
0

非常感谢Dennis Williamson，他通过回答我对 shell 脚本编写的一些相关问题（这里和这里）帮助我达成了这种方法。

以下已知问题：

  1. 它仅适用于 ascii 文件，不适用于二进制文件
  2. 仅当文件中没有换行符时才有效
  3. 随着文件变长，它需要的时间呈指数增长
  4. 它很容易在超过几 kb 的文件上中断（用完 tmp 磁盘空间）

如您所见，它是一种巨大的蛮力方法——根本不是一种智能算法。我已经记录了一些示例文件所花费的时间。

bytes  time(s)
204 1.281
407 24.916
610 269.302

甚至像我在下面所做的那样这样做的重点对我来说更多的是“思想挑战”——在 shell 环境中以尽可能“完整”的方式做到这一点。而已。当然，正如结果所示，它的效率极低，因此完全不适合实际应用。

filesize=`stat -c %s $1`
while [ $filesize -gt 1 ]
do
        filesize=`expr $filesize - 1`
        array=( "${array[@]}" $(cat $1 | sed -n ":a;/^.\{$filesize\}$/{p;b};s/.\{$filesize\}/&\n/;P;s/.//;s/\n//;ba" | sort | uniq -c | grep -v '      1' | cut -c9-) )
done

sample=$(<$1)
tag=0;
for entry in ${array[@]};
        do
        test="<[^>/]*>[^>]*$entry[^<]*</";
        if [[ ! $sample =~ $test ]];
                then ((tag++));
                sample=${sample//${entry}/<T$tag>$entry</T$tag>};
        fi;
        done;
echo $sample

用法如下：

sh tagwords4 sample2.txt
于 2010-07-13T10:16:07.303 回答