试图整一个自己的模板列表
|
497
|
0
|
技术交流

1179 字
|
40 分钟

前言

转眼间就到了寒假，9h6的训练强度瞬间就填充了无聊的假期的大部分时间。在这个假期里有件事做也不至于过于颓废，故决定在刷题补题听网课的同时，整理可以在线下级考试使用的模板大全。
挂在博客上主要是图那个自动生成的跳转目录（雾）

线段树

简易的函数版本（）

#include<bits/stdc++.h>
#define LS (k<<1)
#define RS ((k<<1)|1)
#define mid ((l+r)>>1)
using namespace std;
int n,m,opt;long long a,b,c;
long long ai[400005],tag[400005],sum[400005];

void push_up(int k){
    sum[k]=sum[LS]+sum[RS];
}

void _add(int k,int l,int r,long long v){
    tag[k] += v;
    sum[k] += v*(r-l+1);
}

void push_down(int k,int l,int r){
    if(tag[k]==0)return;
    _add(LS,l,mid,tag[k]);
    _add(RS,mid+1,r,tag[k]);
    tag[k]=0;
}

void build(int k,int l,int r){
    tag[k]=0;
    if(l==r){
        sum[k]=ai[l];
        return;
    }
    build(LS,l,mid);
    build(RS,mid+1,r);
    push_up(k);
}

void add(int k,int l,int r,int x,int y,long long v){
    if(x<=l && r<=y){
        _add(k,l,r,v);
        return;
    }
    push_down(k,l,r);
    if(x<=mid) add(LS,l,mid,x,y,v);
    if(mid<y)  add(RS,mid+1,r,x,y,v);
    push_up(k);
}

long long query(int k,int l,int r,int x,int y){
    if(x<=l && r<=y){
        return sum[k];
    }
    push_down(k,l,r);
    long long res = 0;
    if(x<=mid) res += query(LS,l,mid,x,y);
    if(mid<y)  res += query(RS,mid+1,r,x,y);
    return res;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&ai[i]);
    }
    build(1,1,n);
    for(int i=1;i<=m;i++){
        scanf("%d%lld%lld",&opt,&a,&b);
        switch(opt){
            case 1:{
                scanf("%lld",&c);
                add(1,1,n,a,b,c);
                break;
            }
            case 2:{
                printf("%lld\n",query(1,1,n,a,b));
                break;
            }
            case 3:{
                for(int i=1;i<=n;i++){
                    printf("%lld ",query(1,1,n,i,i));
                }
                printf("\n");
                break;
            }
        }
    }
}

花哨的类版本

//////////////////////////////////////////
// File     : segTreeLazyTag.hpp
// Author   : zhtg
// Create   : 2022.10.12
// Comments : Segment tree with lazy tag.
//////////////////////////////////////////

#include <vector>
//#define MODIFY // 是否以直接修改区间节点代替区间加减
using namespace std;

template <typename T>
class segTree{
  private:
    vector<T>    seg;
    vector<T>    tag;
    #ifdef MODIFY
    vector<bool> flag;
    #endif
    int sz,segsz;
    vector<T> def;

  private:
    void __build(auto l,auto r,auto p,vector<T>& ai){
      if(l==r){
        seg[p] = ai[l];
        return;
      }
      auto m=(l+r)>>1;
      __build(l,m,p*2,ai);
      __build(m+1,r,p*2+1,ai);
      seg[p] = seg[p*2] + seg[p*2+1];
    }
  public:
    segTree(vector<T>& ai){
      sz = ai.size();
      segsz = 4*(ai.size()+5);
      seg.resize(segsz);
      tag.resize(segsz);
    #ifdef MODIFY
      flag.resize(segsz);
    #endif
      __build(0,sz - 1,1,ai);
    }
    segTree(int n=1){
      sz = n;
      segsz = 4*(sz+5);
      seg.resize(segsz);
      tag.resize(segsz);
      def.resize(sz);
    #ifdef MODIFY
      flag.resize(segsz);
    #endif
      __build(0,sz - 1,1,def);
    }
  #ifdef MODIFY   //启用编辑模式
    void update(auto l,auto r,T val,auto s=0,auto t=sz-1,auto p=1){
      if(l<=s && t<=r){
        seg[p] = (t-s+1)*val, tag[p] = val;
        return;
      }
      auto m = (s + t) >> 1;
      if(flag[p]){
        seg[p*2] = (m-s+1) * tag[p],
        seg[p*2+1] = (t-m) * tag[p];
        tag[p*2] = tag[p*2+1] = tag[p];
        flag[p*2] = flag[p*2+1] = true;
        flag[p] = false;
      }
      if(l<=m) update(l,r,val,s,m,p*2);
      if(m<r)  update(l,r,val,m+1,t,p*2+1);
      seg[p] = seg[p*2] + seg[p*2+1];
    }
    T getsum(auto l,auto r,auto s=0,auto t=sz-1,auto p=1){
      if(l<=s && t<=r){
        return seg[p];
      }
      auto m = (s + t) >> 1;
      if(flag[p]){
        seg[p*2] = (m-s+1) * tag[p],
        seg[p*2+1] = (t-m) * tag[p];
        tag[p*2] = tag[p*2+1] = tag[p];
        flag[p*2] = flag[p*2+1] = true;
        flag[p] = false;
      }
      T sum = 0;
      if(l<=m) update(l,r,s,m,p*2);
      if(m<r)  update(l,r,m+1,t,p*2+1);
      return sum;
    }
  #else           //启用累加模式
    void update(auto l,auto r,T val,auto s=0,auto t=sz-1,auto p=1){
      if(l<=s && t<=r){
        seg[p] += (t-s+1)*val, tag[p] += val;
        return;
      }
      auto m = (s + t) >> 1;
      if(tag[p] && s!=t){
        seg[p*2] += (m-s+1) * tag[p],
        seg[p*2+1] += (t-m) * tag[p];
        tag[p*2] += tag[p];
        tag[p*2+1] += tag[p];
        tag[p] = 0;
      }
      if(l<=m) update(l,r,val,s,m,p*2);
      if(m<r)  update(l,r,val,m+1,t,p*2+1);
      seg[p] = seg[p*2] + seg[p*2+1];
    }
    T getsum(auto l,auto r,auto s=0,auto t=sz-1,auto p=1){
      if(l<=s && t<=r){
        return seg[p];
      }
      auto m = (s + t) >> 1;
      if(tag[p]){
        seg[p*2] += (m-s+1) * tag[p],
        seg[p*2+1] += (t-m) * tag[p];
        tag[p*2] += tag[p];
        tag[p*2+1] += tag[p];
        tag[p] = 0;
      }
      T sum = 0;
      if(l<=m) update(l,r,s,m,p*2);
      if(m<r)  update(l,r,m+1,t,p*2+1);
      return sum;
    }
  #endif
};

Graph 图论

树的欧拉序

/**************************
 * 树的欧拉序
 * HINT : 在欧拉序的一个连续区间内的
 *        所有点集s均在同一个连通块
 * INIT : dfs(ROOT, 0)
 * CALL : olah[i] = j
 *         => 点 j 的欧拉序为 i
***************************/
int head[2005],nxt[5005],to[5005],vcnt=0;
int olah[5005],olahcnt=0,maxgcd=0,a,b,n,c;

void dfs(int cur,int fa){
    olah[++olahcnt] = cur;
    for(int i=head[cur];i!=-1;i=nxt[i]){
        if(to[i]==fa) continue;
        dfs(to[i],cur);olah[++olahcnt]=cur;
    }
}

图的欧拉回路

/**************************
 * 图的欧拉回路
 * HINT : 找出通过图中每条边恰好一次的回路
 * INIT : __init(); dfs(0);
 * CALL : ansi[]
 *         => 遍历节点的先后顺序
***************************/
namespace lovelive{
    const int MAXN = 10005, MAXM = 100005;
    int dfn[MAXN],low[MAXN],sta[MAXN];
    int statop,cnt;
    vector<stack<int> > edge;
    vector<int> ansi;
    int n,m,a,b;
    void __init(){
        statop = cnt = 0;
        edge.clear();
        edge.resize(n+1);
        ansi.clear();
        memset(dfn,0,sizeof(dfn));
    }
    void addEdge(int u,int v){
        edge[u].push(v);
        edge[v].push(u);
    }
    void dfs(int cur){
        while(!edge[cur].empty()){
            int to = edge[cur].top();
            edge[cur].pop();
            dfs(to);
        }
        ansi.push_back(cur);
    }
}

Dijkstra 优化版 O(E*log(E))

namespace lovelive{
    const int MAXN = 205;
    const int MAXM = 100005;
    int head[MAXN],nxt[MAXM],to[MAXM],val[MAXM],cnt;
    int dis[MAXN];

    void dijkstra(int source){
        /******************************
         * dijkstra (pri_queue)
         * Init: Graph(H:N:T:V), source
         * Call: dijkstra(source)
         * Resu: di[i]
         * Comm: 从source到各点距离
         *       不存在通路则为-1
        \******************************/
        priority_queue<pair<int,int>> q;
        bool vis[MAXN];
        memset(dis,-1,sizeof(dis));
        memset(vis,0,sizeof(vis));
        dis[source] = 0;
        q.push({0,source});
        while(!q.empty()){
            int cur = q.top().second;q.pop();
            if(vis[cur])continue;
            vis[cur] = true;
            for(int i=head[cur],v;i!=-1;i=nxt[i]){
                v = to[i];
                if((dis[v]==-1 || dis[v]>dis[cur]+val[i])){
                        dis[v] = dis[cur] + val[i];
                        q.push({-dis[v],v});
                }
            }
        }
    }
}

SPFA O(nm)

/**************************
 * SPFA 最大时间复杂度 O(nm)
 * HINT : 找出可能存在负环的有向图的最短路
 * INIT : spfa(n, root); 
 * CALL : dis[]
 *  => 该节点距离root最短路长度
***************************/
struct edge {
  int v, w;
};

vector<edge> e[maxn];
int dis[maxn], cnt[maxn], vis[maxn];
queue<int> q;

bool spfa(int n, int s) {
  memset(dis, 63, sizeof(dis));
  dis[s] = 0, vis[s] = 1;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop(), vis[u] = 0;
    for (auto ed : e[u]) {
      int v = ed.v, w = ed.w;
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        cnt[v] = cnt[u] + 1;  // 记录最短路经过的边数
        if (cnt[v] >= n) return false;
        // 在不经过负环的情况下，最短路至多经过 n - 1 条边
        // 因此如果经过了多于 n 条边，一定说明经过了负环
        if (!vis[v]) q.push(v), vis[v] = 1;
      }
    }
  }
  return true;
}

最小生成树 Kruskal

/******************************
 * 最小生成树 Kruskal
 * Init: Graph(edge<dis,<ai,aj>>), fa[i]=i
 * Call: kruskal()
 * Resu: 在该例中返回值为最小生成树边权和
 * Comm: 找出无向图中的边权和最小的树（的边权和）
\******************************/
namespace lovelive{
    typedef pair<double,pair<int,int> > E;
    const int MAXN = 1005;
    const int MAXM = MAXN * MAXN;

    E edge[MAXM];
    int fa[MAXN],n,edgecnt;

    void init(){
        for(int i=1;i<=n;i++){
            fa[i] = i;
        }
    }
    int getfa(int p){
        if(fa[p]==p)return p;
        return fa[p] = getfa(fa[p]);
    }
    double kruskal(){
        int flag,a,b,ta,tb;
        double ans;flag = 0;ans = 0;
        sort(edge+1,edge+edgecnt+1);

        for(int i=1;i<=edgecnt;i++){
            a = edge[i].second.first;
            b = edge[i].second.second;
            ta = getfa(a);
            tb = getfa(b);
            if(ta==tb)continue;
            fa[ta] = tb;
            ans += edge[i].first;
            flag ++;
            if(flag==n-1)break;
        }
        return ans;
    }
}

Tarjan求强连通分量

/******************************
 * Tarjan求强连通分量
 * Init: Graph(H:N:T) => init()
 * Call: tarjan(root)
 * Resu: color[i] => 染色信息
 * Comm: 对于指定图进行缩点，对于缩点后
 *       的同一个点染上同一个颜色
\******************************/
namespace lovelive{
    typedef int VAL;
    const int MAXN = 10005;
    const int MAXM = 200005;
    int head[MAXN],nxt[MAXM],to[MAXM],cnt;
    int sta[MAXN],dfn[MAXN],low[MAXN],statop,tarcnt;
    VAL val[MAXN];
    int color[MAXN],colorcnt;
    void init(){
        memset(head,-1,sizeof(head));
        memset(color,0,sizeof(color));
        memset(dfn,0,sizeof(dfn));
        cnt = statop = tarcnt = colorcnt = 0;
    }
    void tarjan(int cur){
        dfn[cur] = low[cur] = ++tarcnt;
        sta[++statop] = cur;
        for(int _i=head[cur],t;_i>=0;_i=nxt[_i]){
            t = to[_i];
            if(!dfn[t]){
                tarjan(t);
                low[cur] = min(low[cur],low[t]);
            }else if(!color[t]){
                low[cur] = min(low[cur],dfn[t]);
            }
        }
        if(dfn[cur] == low[cur]){
            color[cur] = ++colorcnt;
            /* 该颜色对应点的操作 */
            while(sta[statop]!=cur){
                color[sta[statop]] = colorcnt;
                /* 该颜色对应点的操作 */
                statop--;
            }
            statop--;
        }
    }
}

Tarjan求割点

/******************************
 * Tarjan求割点
 * Init: Graph(H:N:T) => init()
 * Call: tarjan(root,root)
 * Resu: flag[i] => 该点是否为割点
 *       res     => 割点的数量
 * Comm: 运用tarjan求出割点
\******************************/
namespace lovelive{
    typedef int VAL;
    const int MAXN = 10005;
    const int MAXM = 200005;
    int head[MAXN],nxt[MAXM],to[MAXM],cnt;
    int dfn[MAXN],low[MAXN],tarcnt,res;
    bool flag[MAXN],vis[MAXN];
    void init(){
        memset(head,-1,sizeof(head));
        memset(flag,0,sizeof(flag));  //flag指其是否为割点
        memset(vis,0,sizeof(vis));    //vis记录是否已重复
        memset(dfn,0,sizeof(dfn));
        cnt = tarcnt = res = 0;
    }
    void tarjan(int cur,int fa){
        dfn[cur] = low[cur] = ++tarcnt;
                    //此处low特指该节点不通过dfs父亲节点
                    //所能向上回溯到的最祖先的点
        vis[cur] = true;
        int child = 0;
        for(int _i=head[cur],v;_i>=0;_i=nxt[_i]){
            v = to[_i];
            if(!vis[v]){
                child++;
                tarjan(v,cur);
                low[cur] = min(low[cur],low[v]);
                if(fa != cur && low[v]>=dfn[cur] && !flag[cur]){
                    // 如果自己不是起始点
                    // 并且子节点无法不通过当前节点到达更祖先的点
                    // 同时该节点并未被记录过
                    res++;
                    flag[cur] = true;
                }
            }else if(v!=fa){
                //只要不是父亲节点就有可能是合法祖先点
                low[cur] = min(low[cur],dfn[v]);
            }
        }
        if(fa==cur && child>1 && !flag[cur]){
            //特殊情况
            //若当前节点为dfs根节点，那么
            //如果有两个及以上dfs子节点，则
            //它们必须通过该根节点
            res++;flag[cur] = true;
        }
    }
}

最近公共祖先 (LCA) 倍增法

/******************************\
 * 最近公共祖先 (LCA) 倍增法
 * Init: Graph(H:N:T) => dfs(root)
 * Call: lca(ai,bi)
 * Resu: 两点之间的最近公共祖先
 * Comm: 运用倍增算法寻找两点之间的最近公共祖先
\******************************/
namespace lovelive{
    const int MAXN = 1005;
    const int POW  = 21;
    int head[MAXN],nxt[2*MAXN],to[2*MAXN],cnt;
    int fa[POW][MAXN],depth[MAXN];

    void dfs(int cur,int f){
        depth[cur] = depth[f] + 1;
        fa[0][cur] = f;
        for(int i=1;i<POW;i++){
            fa[i][cur] = fa[i-1][fa[i-1][cur]];
        }
        for(int i=head[cur],t;i;i=nxt[i]){
            t = to[i];
            if(t==f)continue;
            dfs(t,cur);
        }
    }
    int lca(int ai,int bi){
        if(depth[ai]<depth[bi])swap(ai,bi);
        for(int i=POW-1;i>=0;i--){
            if(depth[fa[i][ai]]>=depth[bi]){
                ai = fa[i][ai];
            }
            if(ai==bi)return ai;
        }
        for(int i=POW-1;i>=0;i--){
            if(fa[i][ai]!=fa[i][bi]){
                ai = fa[i][ai];
                bi = fa[i][bi];
            }
        }
        return fa[0][ai];
    }
}

String 字符串

Manacher 算法

/******************************\
 * Manacher 算法 O(N)
 * Init: si (char si[])
 * Call: manacher(si)
 * Resu: 返回最大回文串长度
 * Comm: 用于在字符串中快速找出最大回文串
\******************************/
namespace lovelive{
    const int MAXN = 11000005;
    char si[MAXN];
    int manacher(char si[]){
        int d1[MAXN],d2[MAXN];
        int l1,r1,l2,r2,len,j,ans;
        len = strlen(si);
        l1 = 0;r1 = -1;
        l2 = 0;r2 = -1;
        ans = 0;
        for(int i=0;i<len;i++){
            //求奇数长度的回文串的Manacher算法
            //Manacher算法的核心是利用对当前边界最右侧
            //的已知回文串的已知信息进行记忆化
            if(i>r1){                   //当前在回文串外面
                d1[i]=1;                //直接使用朴素算法
                while(i-d1[i]>=0 && i+d1[i]<len && si[i-d1[i]]==si[i+d1[i]]){
                    d1[i]++;
                }
            }else{                      //当前在回文串里面
                j = l1 + r1 - i;        //搜索当前回文串的对称位置
                                        //在当前位置之前的回文串都处理完毕了
                                        //所以现在肯定在回文串的后半段
                if(i+d1[j]-1 >= r1){    //如果对称位置的回文串边界超出了当前回文串的边界
                    d1[i] = r1 - i + 1; //不能轻举妄动，因为回文串外的回文性未知
                    while(i-d1[i]>=0 && i+d1[i]<len && si[i-d1[i]]==si[i+d1[i]]){
                        d1[i]++;
                    }                   //喜闻乐见的朴素算法
                }else{
                    d1[i] = d1[j];      //没问题就直接用，没关系的
                }
            }//接下来就该记录答案了
            //无论如何请不要忘记更新边界值
            if(r1==-1 || r1<i+d1[i]-1) r1 = i+d1[i]-1, l1 = i-d1[i]+1;
            ans = max(ans,2*d1[i]-1);

            //求偶数长度的回文串的Manacher算法
            //与奇数版本基本相同，注意相关计算的更改
            //这里选择在偶数长度回文串的右中心记录值
            if(i>r2){
                d2[i] = 0;              //偶数长度回文可能不存在，初始置0
                while(i-d2[i]-1>=0 && i+d2[i]<len && si[i-d2[i]-1]==si[i+d2[i]]){
                    d2[i]++;
                }
            }else{
                j = l2 + r2 - i + 1;    // * * ! * + + * * ! *
                                        // 0 1 2 3 4 5 6 7 8 9  
                if(i+d2[j]-1 >= r2){
                    d2[i] = r2 - i + 1;
                    while(i-d2[i]-1>=0 && i+d2[i]<len && si[i-d2[i]-1]==si[i+d2[i]]){
                        d2[i]++;
                    }
                }else{
                    d2[i] = d2[j];
                }
            }
            //偶数长度回文串可能不存在
            if(d2[i] && r2<i+d2[i]-1) r2 = i+d2[i]-1, l2 = i-d2[i];
            ans = max(ans,2*d2[i]);
        }
        return ans;
    }
}

字符串前缀函数

众多字符串实现算法需要的的基本函数，包括但不限于KMP等。

/******************************\
 * 字符串前缀函数 O(N)
 * Init: s (string)
 * Call: prefix_func(s)
 * Resu: 以函数返回值返回前缀函数数组res[i]
 * Comm: 对于每一个子串s[0:i+1)最长的
         相等的真前缀与真后缀的长度。
\******************************/
namespace lovelive{
    typedef vector<int> VEC;
    VEC prefix_func(string s){
        int len = s.size(), j;
        VEC res(len);
        for(int i=1;i<len;i++){
            j = res[i-1];
            while(j & s[i]!=s[j]){
                j = res[j-1];
            }
            if(s[i]==s[j])j++;
            res[i] = j;
        }
        return res;
    }
}

Knuth-Morris-Pratt (KMP) 算法

使用string

玄学错误警告
该代码在测试运行的时候出现了玄学错误（本地通过而洛谷WA的情况），请谨慎使用该版本代码。
/******************************\
 * KMP算法 O(N)
 * Init: source, target (string)
 * Call: kmp(source, target)
 * Resu: 以函数返回值返回所有起始位置
 * Comm: 找出source中所有的target子串
\******************************/
namespace lovelive{
    typedef vector<int> VEC;
    // 【前置函数】  字符串前缀函数
    // VEC prefix_func(string s);
    VEC kmp(string source,string target){
        string cur = target + "#" + source;
        int szs = source.size();
        int szt = target.size();
        VEC res, pref = prefix_func(cur);
        //如果想转成在线算法或者空间卡常也很简单，
        //前缀函数参数只写source+"#"，
        //然后在剩下的部分复现前缀函数并只记录当前值
        //因为处理字符串的前缀函数，值不会大于szt
        for(int i=szt+1;i<=szt+szs;i++){
            if(pref[i]==szt){
                res.push_back(i - 2*szt);
            }
        }
        return res;
    }
}

纯char数组版本（string不使用）

如果上面那版存在卡常风险（2e6一定会卡），请使用这一版代码。该代码在洛谷模板题通过测试。

/******************************\
 * KMP算法 O(N) 纯char数组实现版
 * Init: source, target (char[])
 * Call: kmp()
 * Resu: ansi[1:anscnt], pref[]
 * Comm: ansi储存source中所有的target子串起始
         pref储存target的前缀函数值
         该版本用于在奇怪的地方卡常的情况
\******************************/
namespace lovelive{
    const int MAXN = 1000005;
    int pref[MAXN],ansi[MAXN],anscnt;
    int szs,szt;
    char source[MAXN],target[MAXN];
    char nico(int i){
        return i<szt?target[i]:(i==szt?'#':source[i-szt-1]);
    }
    void kmp(){
        int j = 0; anscnt = 0;pref[0] = 0;
        szs = strlen(source);
        szt = strlen(target);
        for(int i=1;i<szt;i++){
            j = pref[i-1];
            while(j>0 & nico(i)!=nico(j)){
                j = pref[j-1];
            }
            if(nico(i)==nico(j))j++;
            pref[i] = j;
        }
        j = 0;
        for(int i=szt+1;i<=szt+szs;i++){
            while(j>0 & nico(i)!=nico(j)){
                j = pref[j-1];
            }
            if(nico(i)==nico(j))j++;
            if(j==szt){
                ansi[++anscnt] = (i - 2*szt);
            }
        }
    }
}

Z 函数 – 使用string

未经验证的代码
该代码由于大概率会卡常，故没有在洛谷模板题进行实测，请谨慎使用该版本代码，仅作为思路参考。
/******************************\
 * Z函数/扩展KMP O(N) - 使用string
 * Init: s (string)
 * Call: z_func(s)
 * Resu: 以函数返回值返回s的Z函数值
 * Comm: 函数z[i]表示s和s[i:n)
         的最长公共前缀（LCP）的长度。
\******************************/
namespace lovelive{
    typedef vector<int> VEC;
    VEC z_func(string s){
        int len = s.size(), l=0, r=0;
        VEC res(len);
        for(int i=1;i<len;i++){
            if(i<=r && res[i-l] < r-i+1){
                res[i] = res[i-l];
            }else{
                res[i] = max(0,r - i + 1);
                while(i+res[i]<len && s[i]==s[i+res[i]]){
                    res[i]++;
                }
            }
            if(i+res[i]-1 > r) l = i, r = i+res[i]-1;
        }
        return res;
    }
}

扩展KMP – 纯char数组

/******************************\
 * Z函数/扩展KMP O(N) - 纯char数组
 * Init: source, target (char[])
 * Call: z_func()
 * Resu: 在res[i]数组中储存s的Z函数值
 * Comm: 函数res[i]表示s和s[i:n)
         的最长公共前缀（LCP）的长度
         其中 s=target+"#"+source
\******************************/
namespace lovelive{
    const int MAXN = 200005;
    char source[MAXN],target[MAXN];
    LL res[MAXN*2];
    int szs,szt;
    inline char nico(int i){
        return i<szt?target[i]:(i==szt?'#':source[i-szt-1]);
    }
    void z_func(){
        int len = szs + szt + 1, l=0, r=0;
        szs = strlen(source);
        szt = strlen(target);
        res[0] = 0;
        for(int i=1;i<len;i++){
            if(i<=r && res[i-l] < r-i+1){
                res[i] = res[i-l];
            }else{
                res[i] = max(0,r - i + 1);
                while(i+res[i]<len && nico(res[i])==nico(i+res[i])){
                    res[i]++;
                }
            }
            if(i+res[i]-1 > r) l = i, r = i+res[i]-1;
            //如果想要用此算法进行KMP，则需要记录出现res[i]==szt的下标
        }
    }
知识共享许可协议
《试图整一个自己的模板列表》在文章中没有特殊说明的情况下采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。请在转载时注明作者（从现瑕疵）和来源（https://www.zhtg.net.cn/templates-list/）
图论搜索算法
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

															
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
数论笔记

							
							

							
蚌埠住了的大模拟专题 (1)

							
							

							
ZJUT2022寒假集训3 字符串1 程序简注

							
							

							
Codeforces Round #841 (Div. 2) 赛后复盘

							
							

							
ZJUT2022寒假集训2 基础专题2 程序简注

							
							

							
ZJUT2022寒假集训1 基础专题1 程序简注

							
							

							
ZJUT2022入门题单Week6 动态规划

							
							

							
Codeforces Round #832 (Div. 2) 解题日志

							
							

							
ZJUT 2022.11.02 Codeforces练习 程序简注

							
							

							
ZJUT2022入门题单Week5 程序简注