回文线性回撤算法

摘要

本发明公开了回文线性回撤算法，所述算法包括以下计算步骤：S1：构建新回文串，所述新回文串是初始化当前回文串为只有两个空节点的串，形成字符串；S2：字符读取，所述读取内容是从字符串中逐一读取字符；S3：字符判断，所述判断内容是读取的当前字符与当前回文是否形成回文；S4：结果统计输出，所述输出的结果是对判断后的结果进行归纳统计，本发明的有益效果是：本发明算法时间和空间复杂度均为线性，其相对于manacher的算法，这个算法可以构造出由不同回文节点组成的树，因此该算法具有更好的结构，更广阔的适用性，能解决更多的实际科学技术，研发，和生产方面等方面的问题。

说明书

技术领域

本发明涉及一种回文算法，具体为回文线性回撤算法，属于计算机算法技术领域。

背景技术

在计算的算法处理中有一种是用于处理回文的算法，现有的计算机用于处理回文的算法大都在n的3次方和2次方，最快的manacher的算法可以在O(n)时间复杂度，而且只能找出最长的回文，不会过滤掉重复的回文，因此在实际的算法计算过程中，现有的这些算法无法直接找到所有不同的回文，这样使得其适用性下降，因此需要提出一种新算法来解决上述问题。

发明内容

本发明的目的就在于为了解决上述问题而提供回文线性回撤算法。

本发明通过以下技术方案来实现上述目的，回文线性回撤算法，所述算法包括以下计算步骤：

S1：构建新回文串，所述新回文串是初始化当前回文串为只有两个空节点的回文，形成的回文串；

S2：字符读取，所述读取内容是从字符串中逐一读取字符；

S3：字符判断，所述判断内容是读取的当前字符与当前回文是否形成回文；

S4：结果统计输出，所述输出的结果是对判断后的结果进行归纳统计。

优选的，所述字符判断包括以下两种结果：

第一种：当前字符与当前回文能形成回文；

第二种：当前字符与当前回文不能形成回文。

优选的，所述当前字符与当前回文能形成回文后，包括以下两个处理过程：

过程一：形成的回文找到过，则记录当前最长回文节点；

过程二：形成的回文没找到过，就生成新回文节点，并且记录为当前最长回文节点，按照回文串回溯寻找下一个回文节点，直到找到过为止，且将这些回文串起来，记录当前最长回文节点。

优选的，所述记录好当前最长回文之后再回复到S2中重新进行字符读取。

优选的，所述当前字符与当前回文不能形成回文后，先通过回文串里回溯下一个回文，然后再回到S3中对该回文进行字符判断。

本发明的有益效果是：

本发明算法时间和空间复杂度均为线性，其相对于manacher的算法，这个算法可以构造出由不同回文节点组成的树，因此该算法具有更好的结构，更广阔的适用性，能解决更多的实际科学技术，研发，和生产方面等方面的问题。

附图说明

图1为本发明整体算法流程示意图；

图2为本发明回文模块示意图。

具体实施方式

下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1，回文线性回撤算法，所述算法包括以下计算步骤：

S1：构建新回文串，所述新回文串是初始化当前回文串为只有两个空节点的回文，形成的回文串；

S2：字符读取，所述读取内容是从字符串中逐一读取字符；

S3：字符判断，所述判断内容是读取的当前字符与当前回文是否形成回文，通过该步骤找到最长回文；

作为本发明的一种技术优化方案，所述字符判断包括以下两种结果：

第一种：当前字符与当前回文能形成回文；

具体的，所述当前字符与当前回文能形成回文后，包括以下两个处理过程：

过程一：形成的回文找到过，则记录当前最长回文节点；

过程二：形成的回文没找到过，就生成新回文节点，并且记录为当前最长回文节点，按照回文串回溯寻找下一个回文节点，直到找到过为止，且将这些回文串起来，记录当前最长回文节点。

所述记录好当前最长回文之后再回复到S2中重新进行字符读取。

第二种：当前字符与当前回文不能形成回文。

具体的，当前字符与当前回文不能形成回文后，先通过回文串里回溯下一个回文，然后再回到S3中对该回文进行字符判断。

S4：结果统计输出，所述输出的结果是对判断后的结果进行归纳统计。

实施例一：参考图2，为本发明回文模块示意图，例如上图回文CBABC，若想找到最长的回文，则必须找出所有不同的回文；

如果对于该字符串，一个字符接着一个字符的找，在找至倒数第二个字符B时，那么到当前字符为止且包括当前字符的最长回文是BAB，第二长的回文是B；把这两个回文串起来，就可以用当前串去找到下一个字符的回文串，直到遍历完所有字符，找到所有的串。

记录回文的时候只需要记录其长度和开始的索引，找下一个回文的时候，只要根据长度算出新的字符相对应的字符，来判断是不是构成回文。构建新回文串的时候要从最长的回文开始，如果新字符基于旧回文已经有匹配的分支，那么就说明这个回文已经有了就不需要再往前回溯，就可以使用匹配的分支的回文及其链串到新串里，如果是新回文，则把这些回文串起来。

实施例二，根据上述算法其通过java来实现该算法的代码为：

此外，应当理解，虽然本说明书按照实施方式加以描述，但并非每个实施方式仅包含一个独立的技术方案，说明书的这种叙述方式仅仅是为清楚起见，本领域技术人员应当将说明书作为一个整体，各实施例中的技术方案也可以经适当组合，形成本领域技术人员可以理解的其他实施方式。