我有一个字符串比如123
我需要输出为
1、2、3、12,13123。
我知道这可以实现使用动态规划。所以我需要帮助。
输入字符串的长度范围是10 ^ 6。
这个问题的变化:My next problem is
我必须只打印那些数字是连续的子集。现在我的答案变成了
1、2、3,23123。注意:13不会出现在这里,因为1和3在输入字符串"123"中不是连续的。
如果不是动态规划,任何其他解决方案也是可以的。记住输入字符串的长度是10^6,所以解应该是0 (length)
提示:考虑使用后缀数组来构建子字符串。使用后缀树可以降低查找O(n)
后缀的复杂性。
一种可能的方法:使用两个循环遍历字符串。外部循环总是在字符串中设置子字符串的开头,内部循环从这个起始位置开始递增,直到字符串的末尾。现在剩下的唯一一件事,就是使用string::operator[]
选择字符串的字符并打印/存储它们或做任何你想做的事情。
编码由你决定;)