首页 > 其他分享 >P3805 【模板】manacher

P3805 【模板】manacher

时间:2024-07-20 14:06:57浏览次数:14  
标签:int manacher s1 rmax long ans P3805 ll 模板

原题链接

题解

细节

所有字符的回文半径初始化为 1
rmax=1
ans=1

code

#include<bits/stdc++.h>
#define ll long long
using namespace std;


void solve()
{
    string s;
    cin>>s;

    string s1;
    for(int i=0;s[i];i++)
    {
        s1+='#';
        s1+=s[i];
    }
    s1+='#';

    ll n=s1.size();
    vector<ll> r(n+5,1);
    ll rmax=0;//和自己匹配肯定是回文串
    ll ans=1,center=0;

    for(int i=0;i<n;i++)
    {
        if(i<rmax) r[i]=min(rmax-i,r[2LL*center-i]);

        while( i-r[i]>=0 && i+r[i]<n &&s1[i+r[i]]==s1[i-r[i]] ) r[i]++;

        if(i+r[i]>rmax)
        {
            center=i;
            rmax=i+r[i];
        }

        if(s1[i]=='#')
        {
            ans=max(ans,r[i]-1);
        }
        else
        {
            ans=max(ans,(r[i]-1)/2*2LL+1);
        }
    }

    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}


标签:int,manacher,s1,rmax,long,ans,P3805,ll,模板
From: https://www.cnblogs.com/pure4knowledge/p/18313048

相关文章

  • 日常记录-FreeMarker模板简单使用
    1.依赖包<dependency>   <groupId>org.freemarker</groupId>   <artifactId>freemarker</artifactId>   <version>2.3.30</version></dependency>2.工具类 importfreemarker.template.Configuration;importfreemarke......
  • P3373 【模板】线段树 2(区间乘+加操作,先乘后加原则)
    题目来源:https://www.luogu.com.cn/problem/P3373//题意:对区间[l,r]可以乘法,加法操作,查询和操作。//思路:既有乘法又有加法,肯定是要有两个标记。纯加法和纯乘法操作是很简单的,但是既有乘法又有加法涉及到先乘后加和先加后乘的顺序。//////所以现在是如何将先加后成也可以......
  • [WesternCTF2018]shrine(Jinja2模板注入)
    首先判断出是Jinja2模板注入判断方法https://www.cnblogs.com/dghh/p/18307622importflaskimportos#创建一个Flask应用实例app=flask.Flask(__name__)#从环境变量中读取'FLAG'并设置到应用配置中app.config['FLAG']=os.environ.pop('FLAG')#定义根路径('/......
  • 易优CMS模板标签uitype栏目调用在模板文件index.htm中调用uitype标签,实现指定栏目可视
    【基础用法】标签:uitype描述:栏目编辑,比uitext、uihtml、uiupload标签多了一个typeid属性,使用时结合html一起才能完成可视化布局,只针对具有可视化功能的模板。用法:<divclass="eyou-edit"e-id="文件模板里唯一的数字ID"e-page='文件模板名'e-type="type">{eyou:uitypetypeid=......
  • 国产linux系统(银河麒麟,统信uos)使用 PageOffice 国产版在线打开 word文件自定义模板中
    国产linux系统(银河麒麟,统信uos)使用PageOffice国产版在线打开pdf文件PageOffice国产版:支持信创系统,支持银河麒麟V10和统信UOS,支持X86(intel、兆芯、海光等)、ARM(飞腾、鲲鹏、麒麟等)芯片架构。本示例关键代码的编写位置Vue+Springboot注意本文中展示的代码均为关键代码,复......
  • 易优CMS模板标签modelsartlist频道循环输出顶级栏目列表
    [基础用法]标签:modelsartlist(channelartlist)备注:使用channelartlist也可以正常输出描述:获取当前栏目分类的下级栏目的文档列表用法:{eyou:modelsartlisttypeid='栏目ID'type='son'loop='20'}<ahref='{eyou:fieldname='typeurl'/}'>{eyou:fi......
  • 模板方法设计模式
    模板方法设计模式:模板方法设计模式:解决方法中存在重复代码的问题。  模板方法设计模式的写法:1、定义一个抽象类2、在里面定义2个方法​一个是模板方法:把相同代码放里面去​一个是抽象方法:具体实现交给子类完成建议使用final关键字修饰模板方法:​模板方......
  • Tarjan模板
    structSCC{inttop=0,cntscc=0,dfncnt=0;vector<int>dfn,low,stk,instk;vector<int>sccnum,sccid;vector<vector<int>>g,scc;SCC(intn){dfn.assign(n+1,0);low.assign(n+1,0......
  • mysql触发器模板
    --当我们对dept表中的数据进行insertdeleteupdate的时候,请将这些操作记录到日志表当中--dept的表结构/*CREATETABLE`dept`(`DEPTNO`intNOTNULLCOMMENT'部门编号',`DNAME`varchar(14)CHARACTERSETutf8mb4COLLATEutf8mb4_0900_ai_ciDEFAULTNULLCOMMEN......
  • c++ primer plus 第16章string 类和标准模板库,16.2.1 使用智能指针
    c++primerplus第16章string类和标准模板库,16.2.1使用智能指针c++primerplus第16章string类和标准模板库,16.2.1使用智能指针文章目录c++primerplus第16章string类和标准模板库,16.2.1使用智能指针16.2.3uniqueptr为何优于autoptr16.2.3unique......