擂台：最长非升序子串的最优化算法

aysten · 发表于 2004-1-6 03:15:10

呵呵，一个老题了。不过拿来给建模选手们看看我觉得还是很有必要的。

问题描述：
给一字符串，仅由小写字母组成并且无空格，如“dfasgsdftffekloeqngalsdfdsaiwerh"，现在要求在这里面找一个个最长的不升序子串。比如下面的例子：
"dfgaeb" --> "fgeb"
请给出一个最快的算法。

注：
升序：顺着abcd...z的顺序为降序
相同的字母向遇既非降序亦非升序。

donms · 发表于 2004-1-6 03:37:02

以下是引用aysten在2004-1-5 19:15:10的发言：
比如下面的例子：
dfgaeb --> fgeb

这个例子有没有问题啊？

itmwk · 发表于 2004-1-6 03:37:16

在我印象里，在《实用算法的分析与程序设计》那本书中见过解此问题的算法

aysten · 发表于 2004-1-6 04:47:28

啊~~~不好意思，写错了，母串是"dhgeab"

donms · 发表于 2004-1-6 05:06:56

那相应的子串呢？

由于要求最优，所以这个算法在母串长度未知的情况下
扫描一遍母串是必须的，而且好像也只需扫描一遍

aysten · 发表于 2004-1-6 05:21:15

"dhgeab"-->"hgea"

你自己先写出来自己测试测试你的算法再说。

[此贴子已经被作者于2004-1-7 20:12:46编辑过]

donms · 发表于 2004-1-6 05:31:52

看了这个例子更糊涂了！
按照我的理解应该是"dhgeab"-->"hgea"

另外这个是笔误吧？

以下是引用aysten在2004-1-5 19:15:10的发言：
升序：顺着abcd...z的顺序为降序

aysten · 发表于 2004-1-6 05:34:27

这难道不是笔误吗？

knight · 发表于 2004-1-6 05:41:27

我想这个可以用代数里面的逆序数的方法去考虑

aysten · 发表于 2004-1-6 06:58:04

动手做做嘛。

		自动登录	找回密码
密码			注-册-帐-号