碼迷,mamicode.com
首頁 > 編程語言 > 詳細

馬拉車算法

時間:2021-07-28 21:25:10      閱讀:0      評論:0      收藏:0      [點我收藏+]

標簽:int   子串   second   line   alt   strlen   inf   ==   根據   

含義

就是一個\(O(n)\)的復雜度求解最長回文子串的算法

思路

思路的話我隨便說下

首先回文串可能是奇數也可能是偶數,那么對稱中心就有可能是兩個字符的空隙,所以先給每個字符插如一個隔板符號 ‘|‘ 第0個字符插入‘~‘ 防止出現超出邊界的問題

abcbs -> ~|a|b|c|b|s|

\(p[i]\)\(i\)為中點的回文半徑包括自己本身

例如|a|b|a| 那么\(p[4]=4\)

我們也維護一個$ mx$ 和 \(id\),表示對于當前計算的\([1,i-1]\)中,\(i + p[i]\) 的最大值是$ mx\(,\)mx \(對應的\) i \(記為\)id$

當你現在開始計算 p[i] 時,默認$ p[1..i-1] $都已經算出。如果 \(mx > i\),那么根據對稱得出

\(p[i] >= min(p[2 \times id - i], mx - i+1)\)

由下圖可以看出

技術圖片

而最后的答案即為\(max(p[i])-1\)

很多人都沒有解釋為什么,其實很簡單

根據\(p[i]\)的定義,那么擴展的回文串的長度即為\(2p[i]-1\)

而其中#\(p[i]\)個,所以原回文串的長度即為\(p[i]-1\)

這個算法挺簡單的,感覺比kmp都要簡單很多

模板題

代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=2e7+5,inf=0x3f3f3f3f,mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-7;
char temp[maxn];
char s[maxn];
int p[maxn];
int main(){
    scanf("%s",temp+1);
    int n=strlen(temp+1);
    n=2*n+1;
    s[0]=‘~‘;
    for(int i=1;i<=n;i++){
        if(i%2){
            s[i]=‘|‘;
        }else{
            s[i]=temp[i/2];
        }
    }
    int mx=0,id=1,ans=0;
    for(int i=1;i<=n;i++){
        p[i]=min(p[2*id-i],mx-i+1);
        while(s[i+p[i]]==s[i-p[i]]) p[i]++;
        if(p[i]+i-1>=mx){
            mx=p[i]+i-1;
            id=i;
            ans=max(ans,p[i]-1);
        }
    }
    printf("%d\n",ans);
    return 0;
}

馬拉車算法

標簽:int   子串   second   line   alt   strlen   inf   ==   根據   

原文地址:https://www.cnblogs.com/hunxuewangzi/p/15068080.html

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 mamicode.com 版權所有  聯系我們:gaon5@hotmail.com
迷上了代碼!
4399在线看MV_久久99精品久久久久久久久久_成人又黄又爽又刺激视频_能收黄台的app不收费