[發明專利]回文線性回撤算法

在審

• 申請號: 202210409473.1
• 申請日: 2022-04-19
• 公開（公告）號: CN114781326A
• 公開（公告）日: 2022-07-22
• 發明（設計）人: 許家統
• 申請（專利權）人: 許家統
• 主分類號: G06F40/12
• 分類號: G06F40/12;G06F16/903
• 代理公司: 暫無信息
• 代理人: 暫無信息

本發明公開了回文線性回撤算法，所述算法包括以下計算步驟：S1：構建新回文串，所述新回文串是初始化當前回文串為只有兩個空節點的串，形成字符串；S2：字符讀取，所述讀取內容是從字符串中逐一讀取字符；S3：字符判斷，所述判斷內容是讀取的當前字符與當前回文是否形成回文；S4：結果統計輸出，所述輸出的結果是對判斷后的結果進行歸納統計，本發明的有益效果是：本發明算法時間和空間復雜度均為線性，其相對于manacher的算法，這個算法可以構造出由不同回文節點組成的樹，因此該算法具有更好的結構，更廣闊的適用性，能解決更多的實際科學技術，研發，和生產方面等方面的問題。

技術領域

本發明涉及一種回文算法，具體為回文線性回撤算法，屬于計算機算法技術領域。

背景技術

在計算的算法處理中有一種是用于處理回文的算法，現有的計算機用于處理回文的算法大都在n的3次方和2次方，最快的manacher的算法可以在O(n)時間復雜度，而且只能找出最長的回文，不會過濾掉重復的回文，因此在實際的算法計算過程中，現有的這些算法無法直接找到所有不同的回文，這樣使得其適用性下降，因此需要提出一種新算法來解決上述問題。

發明內容

本發明的目的就在于為了解決上述問題而提供回文線性回撤算法。

本發明通過以下技術方案來實現上述目的，回文線性回撤算法，所述算法包括以下計算步驟：

S1：構建新回文串，所述新回文串是初始化當前回文串為只有兩個空節點的回文，形成的回文串；

S2：字符讀取，所述讀取內容是從字符串中逐一讀取字符；

S3：字符判斷，所述判斷內容是讀取的當前字符與當前回文是否形成回文；

S4：結果統計輸出，所述輸出的結果是對判斷后的結果進行歸納統計。

優選的，所述字符判斷包括以下兩種結果：

第一種：當前字符與當前回文能形成回文；

第二種：當前字符與當前回文不能形成回文。

優選的，所述當前字符與當前回文能形成回文后，包括以下兩個處理過程：

過程一：形成的回文找到過，則記錄當前最長回文節點；

過程二：形成的回文沒找到過，就生成新回文節點，并且記錄為當前最長回文節點，按照回文串回溯尋找下一個回文節點，直到找到過為止，且將這些回文串起來，記錄當前最長回文節點。

優選的，所述記錄好當前最長回文之后再回復到S2中重新進行字符讀取。

優選的，所述當前字符與當前回文不能形成回文后，先通過回文串里回溯下一個回文，然后再回到S3中對該回文進行字符判斷。

本發明的有益效果是：

本發明算法時間和空間復雜度均為線性，其相對于manacher的算法，這個算法可以構造出由不同回文節點組成的樹，因此該算法具有更好的結構，更廣闊的適用性，能解決更多的實際科學技術，研發，和生產方面等方面的問題。

附圖說明

圖1為本發明整體算法流程示意圖；

圖2為本發明回文模塊示意圖。

具體實施方式

下面將結合本發明實施例中的附圖，對本發明實施例中的技術方案進行清楚、完整地描述，顯然，所描述的實施例僅僅是本發明一部分實施例，而不是全部的實施例。基于本發明中的實施例，本領域普通技術人員在沒有做出創造性勞動前提下所獲得的所有其他實施例，都屬于本發明保護的范圍。

請參閱圖1，回文線性回撤算法，所述算法包括以下計算步驟：