Code golf:重复文字的"颜色突出显示"

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>

---

获胜者,冠军:

• 最优雅的解决方案获胜(由其他评论评判,赞成)
• 使用shell脚本的解决方案的奖励积分/考虑因素

---

轻微澄清:

• 输入可以是硬编码或从文件中读取
• 标准仍然是"优雅",虽然它有点模糊,但它也包含简单的字符/行数.其他人和/或赞成者的评论也表明了SO社区如何看待这一挑战

Answer 1

我认为你可以使用反向引用来做到这一点。请参阅这篇文章：正则表达式来检测字符串中的重复 我已经做了很多尝试，目前我有这个表达式：#([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实体，注释说它返回一个整数，但我们不知道它代表什么......），如果它仍然不起作用，你可以尝试实现维基百科的伪代码。