string - コードゴルフ：繰り返されるテキストの「カラーハイライト」

Question

(重要な概念を支援してくれた以下の 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>

---

勝者：

• 最もエレガントなソリューションが勝ちます (他のコメント、賛成票によって判断されます)
• シェルスクリプトを利用したソリューションのボーナスポイント/考慮事項

---

軽微な説明:

• 入力はハードコーディングするか、ファイルから読み取ることができます
• 基準は「エレガンス」のままで、確かに少しあいまいですが、単純な文字/行数もカプセル化しています。他の人によるコメントや賛成票も、SO コミュニティが課題をどのように見ているかを示しています

Answer 1

パール206、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>
================================================================================

Answer 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私はeをssimプライします。1500年代以来、未知のタガルyスクラムディオマケアc b以来. _ _dummytextoftheprintingandtypesttingindustryLoremIpsumentheindustryssanddummytextertheheprinterookleoftpeandletttypespeimenook

PS。誰かが文句を言ったので、入力ステートメントと出力ステートメントを追加しました。混乱して申し訳ありませんが、私には明らかなように思えました。どうやらそうではないので、プレフィックス/トレーラー ステートメントを追加しました。これは、問題の仕様では必要なく、コードの長さにカウントされるべきではありません。

Answer 3

Haskell ：343/344 403 420445485 文字

指数アルゴリズムを使用している場合の文字数は343ですが、2次アルゴリズムを使用している場合は344です。

投稿されたコードは2次コードです。指数アルゴリズムの場合、コード内で1回出現する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>

Answer 4

これを行うには、バックリファレンスを使用できると思います。この投稿を参照してください：文字列内の繰り返しを検出するための正規表現 私は多くの試みを行いましたが、今のところ次の式があります：＃（[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-実装/（修正する必要があり、htmlエンティティが含まれており、コメントには整数が返されると書かれていますが、それが何を表しているのかわかりません...）、それでも機能しない場合は、実装を試みることができますウィキペディアの疑似コード。

Answer 5

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] &]

Answer 6

シェル スクリプトに関するいくつかの関連する質問に答えて、このアプローチにたどり着くのを手伝ってくれたDennis Williamsonに感謝します。

以下の既知の問題:

1. ASCIIファイルでのみ機能し、バイナリファイルでは機能しません
2. ファイルに改行がない場合にのみ機能します
3. ファイルが長くなるにつれて指数関数的に時間がかかります
4. 数キロバイトを超える長さのファイルでは簡単に壊れます (tmp ディスク領域が不足します)。

ご覧のとおり、これは巨大な力ずくの方法であり、スマートなアルゴリズムではありません。いくつかのサンプル ファイルの所要時間を記録しました。

bytes  time(s)
204 1.281
407 24.916
610 269.302

以下で行ったようにこれを行うことのポイントは、シェル環境で可能な限り「完全」な方法でこれを行うという「思考の挑戦」に関するものでした。これ以上何もない。もちろん、結果が示すように、非常に効率が悪いため、実際のアプリケーションにはまったく適していません。

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

Answer 7

パイソン、236 281文字、正規表現なし:)

M2 つ以上のすべての文字列のセットを作成し、それらを反復処理して貪欲な長さの順序で割り当てます

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>.