亚洲春色欧美激情

<form id=WZeJxaBel><nobr id=WZeJxaBel></nobr></form>

<address id=WZeJxaBel><nobr id=WZeJxaBel><nobr id=WZeJxaBel></nobr></nobr></address>

首頁 > 編程語言 > 詳細

馬拉車算法

時間：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）

分享檔案

更多>

2021年07月29日 (22)
2021年07月28日 (40)
2021年07月27日 (32)
2021年07月26日 (79)
2021年07月23日 (29)
2021年07月22日 (30)
2021年07月21日 (42)
2021年07月20日 (16)
2021年07月19日 (90)
2021年07月16日 (35)

周排行

更多

友情鏈接

蘭亭集智國之畫百度統計站長統計阿裏雲 chrome插件新版天聽網

關于我們 - 聯系我們 - 留言反饋

? 2014 mamicode.com 版權所有聯系我們:gaon5@hotmail.com

迷上了代碼！

"I acquaint the inhabitants of Liège of this, that they may understand what fate threatens them if they should assume a similar attitude. A raiding party of hostiles had passed near the fort, and had killed, with particular atrocity, a family of settlers. The man and his wife had been tortured to death, the baby had had its brains beaten out against the trunk of a tree, a very young child had been hung by the wrist tendons to two meat hooks on the walls of the ranch-house, and left there to die. One big boy had had his eyelids and lips and nose cut off, and had been staked down to the ground with his remains of a face lying over a red-ant hole. Only two had [Pg 196]managed to escape,—a child of ten, who had carried his tiny sister in his arms, twenty miles of ca?ons and hills, to the post. Every engine of the English Court was put in motion to prevent the Electoral Prince from coming. Oxford had an interview with Schutz, in which he repeated that it was his applying for the writ to the Lord Chancellor instead of to the queen that had done all the mischief; that her Majesty, had it not been for this untoward incident, would have invited the Prince to come over and spend the summer in England—forgetting, as Schutz observed, that the minute before he had assured him that the queen was too much afraid of seeing any of that family here. He advised Schutz—who could not be convinced that he had done anything irregular in his application, quoting numerous proofs to show that it was the accustomed mode of applying for writs—to avoid appearing again at Court; but Schutz, not seeming disposed to follow that advice, immediately received a positive order to the same effect from the queen through another channel. Schutz, therefore, lost no time in returning to Hanover to justify himself. At the same time, Lord Strafford was instructed to write from the Hague, blaming the conduct of Schutz in applying for the writ in the manner he did, as disrespectful to the queen; for, though strictly legal for an absent peer to make such application, the etiquette was that he should defer it till he could do it personally. Strafford ridiculed the idea of any movement being afoot in favour of the Pretender, and observed that, as to sending him out of the Duke of Lorraine's territory, it was not practicable, because the French king maintained that he had fulfilled the treaty, Lorraine not being any part of France. On the other hand, there were striking signs that the cause[17] of Hanover was in the ascendant. Men who watched the course of events decided accordingly. Marlborough, who so lately had been making court to the Pretender, now wrote from Antwerp, urging the House of Hanover to send over the prince without delay to England; that the state of the queen's health made prompt action necessary; and that the presence of the prince in London would secure the succession without risk, without expense, and without war, and was the likeliest measure of inducing France to abandon its design of assisting the Pretender. Shorty had been frantically trying to catch the Deacon's eye, and was making all manner of winks and warning gestures without avail, for the Deacon answered frankly: "Sure you do," Dodd said, and his voice began to rise. He went to the bed, walked along its length to the window, as he talked, never facing Albin. "You know how to make me feel just fine, no worries at all, no complications, just a nice, simple life. With nothing at all in it, Albin. Nothing at all." J. O., I mean it. "Good-bye, my Bluebell, farewell to you, "Cudn't spare one hand to fetch over fifteen—that's a valiant idea. Now d?an't go loitering; fetch out your cattle afore they're roast beef, git out the horses and all the stock—and souse them ricks wot ?un't burning yit." "Do you know my voice?" asked one of Wells's companions. HoME 亚洲春色欧美激情 ENTER NUMBET 0010www.080322.org.cn
30007.com.cn
aac12.com.cn
www.androidshouyin.com.cn
jingmeidz.com.cn
p14.com.cn
www.sparkoni.org.cn
stuphy.com.cn
www.zjcydq.com.cn
www.zuolihongl.com.cn