Думаю, для этого можно использовать обратные ссылки . См. Это сообщение: Регулярное выражение для обнаружения повторения в строке Я сделал много попыток, и на данный момент у меня есть это выражение: # ([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-сущности , а в комментарии говорится, что он возвращает целое число, но мы не знаем, что оно представляет ...), если это все еще не работает, вы можете попробовать реализовать псевдокод Википедии.

Perl 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>
================================================================================

Python, 236 281 символов, без REGEX :)

Делает набор 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

Выдает, как и ожидалось:

LoremIpsumissimplydummytextoftheprintingandtypesettingindustry. LoremIpsumhasbeentheindustry'sstandarddummytexteversincethe1500s, whenanunknownprintertookagalleyoftypeandscrambledittomakeatypespecimenbook.

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

Что более читабельно на этой вики, выделено следующим образом:

LoremIpsum i ss im ply dummytext oft he print ing и типы e tt ing промышленность . LoremIpsum hasbe en the industry ' ss t и ard dummytext ev er с 1500-х годов, w he nanunknown print er t ook agal le y oft y pe и scramb le di tt omakea типы pe c im en b ook .

PS. Кто-то пожаловался, поэтому я добавил операторы ввода и вывода. Приношу свои извинения растерянным - мне это показалось очевидным. По-видимому, нет, поэтому я добавил операторы префикса / трейлера, которые не требуются спецификацией проблемы и не должны учитываться в длине кода.

Haskell: 343/344 403 420 445 485 символов

Количество символов равно 343 при использовании экспоненциального алгоритма, тогда как при использовании квадратичного алгоритма оно равно 344.

Выложенный код - квадратичный. Для экспоненциального алгоритма измените в коде одно вхождение inits=<<хвосты на подпоследовательности.

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>

Mathematica - 262 Chars

Не чистый функционал / Не короткий / Не красивый / Много побочных эффектов.

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

Большое спасибо Dennis Williamson, который помог мне прийти к этому подходу, ответив на несколько связанных вопросов по shell scripting - здесь и здесь.

Известные проблемы:

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