一些常用模板

Defoliation · 2022-07-26 15:42:51 · 个人记录

以下整理了一些常用的算法、技巧、零散知识点等的模板

可能会不定时的进行更新

这也是蒟蒻第一次写博客

如有不完善以及需要补充的地方请指出 谢谢

只要你不失去自己的崇高，整个世界都会为你敞开。

快读:

inline ll read(){   
    ll num=0,f=1;  
    char chr=getchar();
    while(chr<'0'||chr>'9'){   
        if(chr=='-') f=-1;
        chr=getchar();
    }
    while(chr>='0'&&chr<='9'){    
        num=num*10+chr-'0';   
        chr=getchar();
    } 
    return num*f;
}

Kruskal：

#include<bits/stdc++.h>
using namespace std;
const int maxm=2e5+5,maxn=5005;
struct node{
    int u,v,w;
}edge[maxm];
int fa[maxn],n,m,ans,cnt;
bool cmp(node a,node b){
    return a.w<b.w;
}
int find(int x)
{
    if (fa[x]!=x) fa[x]=find(fa[x]);
    return fa[x];
}
void kruskal(){
    sort(edge,edge+m,cmp);
    for(int i=0;i<m;i++){
        if(find(edge[i].u)==find(edge[i].v))            
            continue;
        ans+=edge[i].w;
        fa[find(edge[i].v)]=find(edge[i].u);
        if(++cnt==n-1) break;
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=0;i<m;i++)
        cin>>edge[i].u>>edge[i].v>>edge[i].w;
    kruskal();
    if(cnt==n-1) cout<<ans;
    else cout<<"orz";
    return 0;
}

Borůvka (Sollin):

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+5,maxm=2e5+5;
int n,m;
int u[maxm],v[maxm],w[maxm];
bool used[maxm];
int par[maxn],b[maxn];
int get_par(int x){
    if (x==par[x]) return x;
    else return par[x]=get_par(par[x]);
}
bool Better(int x, int y){
    if(y==0) return true;
    if(w[x]!=w[y]) return w[x]<w[y];
    return x<y;
}
void Boruvka(){
    int merged=0,ans=0;
    bool update=true;
    while(update){
        update=false;
        memset(b,0,sizeof(b));
        for(int i=1;i<=m;++i){
            if(used[i]) continue;
            int p=get_par(u[i]),q=get_par(v[i]);
            if(p==q) continue;
            if(Better(i,b[p])) b[p]=i;
            if(Better(i,b[q])) b[q]=i;
        }
        for(int i=1;i<=n;++i)
            if(b[i]!=0&&used[b[i]]==false){
                update=true;
                merged++; 
                ans+=w[b[i]];
                used[b[i]]=true;
                par[get_par(u[b[i]])]=get_par(v[b[i]]);
            }
    }
    if(merged==n-1) cout<<ans;
    else cout<<"orz";
}

int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=m;++i)
        cin>>u[i]>>v[i]>>w[i];
    for(int i=1;i<=n;++i) par[i]=i;    
    Boruvka();
    return 0;
}

二进制GC:D :

ll gcd(lla,llb)
{
    if(a==0) return b;
    if(!(a&1)&&!(b&1))
        return 2*gcd(a>>1,b>>1);
    else if(!(a&1))
        return gcd(a>>1,b);
    else if(!(b&1))
        return gcd(a,b>>1);
    else
        return gcd(abs(a-b),min(a,b));
}

结构体重载运算符：

• 记住任意一种即可

struct node{  
    int x,y;  
    bool operator<(const node &a)const{  
        return x<a.x;  
    }  
};

struct node{
    int x,y;
    bool friend operator<(node a,node b){
        return a.x>b.x;
    }
};

并查集：

初始化：

int fa[MAXN];
inline void init(int n){
    for(int i=1;i<=n;++i) fa[i]=i;
}

查询（路径压缩）：

int find(int x){
    if(x==fa[x]) return x;
    else{
        fa[x]=find(fa[x]); 
        return fa[x];         
    }
}

int find(int x){
    return x==fa[x]?x:(fa[x]=find(fa[x]));   //简化版本
}

合并：

inline void merge(int i,int j){
    if(rand()&1) swap(i,j);
    fa[find(i)]=find(j);
}

快速幂：

int fastPow(int x,int y){
    int ans=1;
    while(y!=0){
        if(y&1) ans=ans*x;
        x=x*x;
        y>>=1;
    }
    return ans;
}

Dijkstra无优化：

链式前项星存图

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll head[maxn],cnt,dis[maxn],m,n,s,minn;
bool vis[maxn];
struct edge{
    int to,nxt,w;
}edge[maxn];
void addedge(int x,int y,int z){
    edge[++cnt].to=y;
    edge[cnt].w=z;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        addedge(a,b,c);
    }
    int pos=s;
    while(vis[pos]==0){
        minn=2147483647,vis[pos]=1;
        for(int i=head[pos];i!=0;i=edge[i].nxt)
            if(!vis[edge[i].to])
                dis[edge[i].to]=min(dis[edge[i].to],dis[pos]+edge[i].w);
        for(int i=1;i<=n;i++)
            if(dis[i]<minn&&vis[i]==0)
                minn=dis[i],pos=i;
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
}

vector存图

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
ll cnt,dis[maxn],m,n,s,minn;
bool vis[maxn];
struct node{
    int to,w;
};
vector<node>edge[maxn];
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    for(int i=0;i<m;i++){
        int a;
        node e;
        cin>>a>>e.to>>e.w;
        edge[a].push_back(e);
    }
    int pos=s;
    for(int j=1;j<=n;j++){
        minn=2147483647,vis[pos]=1;
        for(int i=0;i<edge[pos].size();i++)
            if(!vis[edge[pos][i].to])
                dis[edge[pos][i].to]=min(dis[edge[pos][i].to],dis[pos]+edge[pos][i].w);
        for(int i=1;i<=n;i++)
            if(dis[i]<minn&&!vis[i])
                minn=dis[i],pos=i;
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
}

Dijkstra堆优化：

链式前项星存图

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll head[maxn],cnt,dis[maxn],m,n,s;
bool vis[maxn];
struct edge{
    int to,nxt,w;
}edge[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void addedge(int x,int y,int z){
    edge[++cnt].to=y;
    edge[cnt].w=z;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        addedge(a,b,c);
    }
    q.push(make_pair(0,s));
    while(q.size()){
        int pos=q.top().second;
        q.pop();
        if(vis[pos]) continue;
        vis[pos]=1;
        for(int i=head[pos];i!=0;i=edge[i].nxt)
            if(!vis[edge[i].to]&&dis[edge[i].to]>dis[pos]+edge[i].w){
                dis[edge[i].to]=dis[pos]+edge[i].w;
                q.push(make_pair(dis[edge[i].to],edge[i].to));
            }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

vector存图

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
ll cnt,dis[maxn],m,n,s;
bool vis[maxn];
struct node{
    int to,w;
};
vector<node>edge[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    dis[s]=0;
    for(int i=1;i<=m;i++){
        int a;
        node e;
        cin>>a>>e.to>>e.w;
        edge[a].push_back(e);
    }
    q.push(make_pair(0,s));
    while(q.size()){
        int pos=q.top().second;
        q.pop();
        if(vis[pos]) continue;
        vis[pos]=1;
        for(int i=0;i<edge[pos].size();i++)
            if(!vis[edge[pos][i].to]&&dis[edge[pos][i].to]>dis[pos]+edge[pos][i].w){
                dis[edge[pos][i].to]=dis[pos]+edge[pos][i].w;
                q.push(make_pair(dis[edge[pos][i].to],edge[pos][i].to));
            }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

Floyd

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
int a[maxn][maxn],n,m,s;
int main(){
    cin>>n>>m>>s;
    memset(a,2147483647,sizeof(a));
    for(int i=1,u,v,w;i<=m;i++){
        cin>>u>>v>>w;
        a[u][v]=min(a[u][v],w);
    }
    a[s][s]=0;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++){
            if(i==k||a[i][k]==2147483647) continue;
            for(int j=1;j<=n;j++)
                a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
        }
    for(int i=1;i<=n;i++) cout<<a[s][i]<<" ";
    return 0;
}

SPFA无优化:

链式前项星存图

#include<bits/stdc++.h>
const int maxn=5e5+5;
using namespace std;
int n,m,s,cnt;
int dis[maxn],head[maxn];
bool vis[maxn];
struct Edge{
    int to,nxt,w;
}edge[maxn]; 
queue<int>q;
void addedge(int x,int y,int z){                              
    edge[++cnt].to=y;
    edge[cnt].w=z;
    edge[cnt].nxt=head[x];
    head[x]=cnt; 
}
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c; 
        addedge(a,b,c);
    }
    q.push(s);dis[s]=0;vis[s]=1;
    while(!q.empty()){
        int pos=q.front(); 
        q.pop();vis[pos]=0; 
        for(int i=head[pos];i;i=edge[i].nxt){
            if(dis[edge[i].to]>dis[pos]+edge[i].w){
                dis[edge[i].to]=dis[pos]+edge[i].w;
                if(!vis[edge[i].to]){
                    vis[edge[i].to]=1; 
                    q.push(edge[i].to);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
    return 0;
} 

vector存图

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
ll cnt,dis[maxn],m,n,s;
bool vis[maxn];
struct node{
    int to,w;
};
vector<node>edge[maxn];
queue<int>q;
int main(){
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=2147483647;
    for(int i=1;i<=m;i++){
        int a;
        node e;
        cin>>a>>e.to>>e.w;
        edge[a].push_back(e);
    }
    q.push(s);dis[s]=0;vis[s]=1;
    while(!q.empty()){
        int pos=q.front(); 
        q.pop();vis[pos]=0; 
        for(int i=0;i<edge[pos].size();i++){
            if(dis[edge[pos][i].to]>dis[pos]+edge[pos][i].w){
                dis[edge[pos][i].to]=dis[pos]+edge[pos][i].w;
                if(!vis[edge[pos][i].to]){
                    vis[edge[pos][i].to]=1; 
                    q.push(edge[pos][i].to);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) cout<<dis[i]<<' ';
    return 0;
}

Johnson 全源最短路:

#include<bits/stdc++.h>
const int maxn=1e5+5;
using namespace std;
struct Edge{
  int to,nxt,w;
}edge[maxn];
int head[maxn],t[maxn],cnt,n,m;
bool vis[maxn];
long long h[maxn],dis[maxn];
void addedge(int x,int y,int z){
    edge[++cnt].to=y;
    edge[cnt].w=z;
    edge[cnt].nxt=head[x];
    head[x]=cnt;
}
bool spfa(int s){
    queue<int>q;
    memset(h,63,sizeof(h));
    h[s]=0;vis[s]=1;q.push(s);
    while(!q.empty()){
        int pos=q.front();
        q.pop();vis[pos]=0;
        for(int i=head[pos];i;i=edge[i].nxt){
            if(h[edge[i].to]>h[pos]+edge[i].w){
                h[edge[i].to]=h[pos]+edge[i].w;
                if(!vis[edge[i].to]){
                    vis[edge[i].to]=1;
                    q.push(edge[i].to);
                    t[edge[i].to]++;
                    if(t[edge[i].to]==n+1) return false;
                }
            }
        }
    }
    return true;
}
void dijkstra(int s){
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
    for(int i=1;i<=n;i++) dis[i]=1e9;
    memset(vis,0,sizeof(vis));
    dis[s] = 0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int pos=q.top().second;
        q.pop();
        if(vis[pos]) continue;
        vis[pos]=1;
        for(int i=head[pos];i;i=edge[i].nxt)
            if(!vis[edge[i].to]&&dis[edge[i].to]>dis[pos]+edge[i].w){
                dis[edge[i].to]=dis[pos]+edge[i].w;
                q.push(make_pair(dis[edge[i].to],edge[i].to));
            }
    }
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        addedge(a,b,c);
    }
    for(int i=1;i<=n;i++) addedge(0,i,0);
    if(!spfa(0)){
        cout<<-1<<endl;
        return 0;
    }
    for(int u=1;u<=n;u++)
        for(int v=head[u];v;v=edge[v].nxt) 
            edge[v].w+=h[u]-h[edge[v].to];
    for(int i=1;i<=n;i++){
        dijkstra(i);
        long long ans=0;
        for(int j=1;j<=n;j++){
            if(dis[j]==1e9) ans+=j*1e9;
            else ans+=j*(dis[j]+h[j]-h[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

次短路：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int dis[maxn],dit[maxn];
int n,m,s,t;
struct node{
    int to,w;
};
vector<node>edge[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void addedge(int x,int y,int z){
    node e;
    e.to=y;e.w=z;edge[x].push_back(e);
}
void dijkstra(){
    for(int i=1;i<=n;i++) dis[i]=1e9,dit[i]=1e9;
    dis[s]=0;
    q.push(make_pair(0,s));
    while(!q.empty()){
        int pos=q.top().second;
        q.pop();
        for(int i=0;i<edge[pos].size();i++){
            if(dis[edge[pos][i].to]>=dis[pos]+edge[pos][i].w){
                dis[edge[pos][i].to]=dis[pos]+edge[pos][i].w;
                q.push(make_pair(dis[edge[pos][i].to],edge[pos][i].to));
            }
            else if(dit[edge[pos][i].to]>dis[pos]+edge[pos][i].w){
                dit[edge[pos][i].to]=dis[pos]+edge[pos][i].w;
                q.push(make_pair(dis[edge[pos][i].to],edge[pos][i].to));
            }
            if(dit[edge[pos][i].to]>edge[pos][i].w+dit[pos])
                dit[edge[pos][i].to]=edge[pos][i].w+dit[pos];
        }
    }
}
int main(){
    cin>>n>>m;
    s=1;
    for(int i=1;i<=m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        addedge(a,b,c);addedge(b,a,c);
    }
    dijkstra();
    cout<<dit[n];
    return 0;
}

线段树：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn=1e6+5;
ll n,m,mod,a[maxn],tree[maxn<<2],lazy_add[maxn<<2],lazy_mul[maxn<<2];
inline ll ls(ll p){return p<<1;}//左子树 
inline ll rs(ll p){return (p<<1)|1;}//右子树 
void build(ll p,ll l,ll r){//建树 
    if(l==r){tree[p]=a[l];lazy_mul[p]=1;tree[p]%=mod;return;}
    ll mid=l+((r-l)>>1);
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
    tree[p]=tree[ls(p)]+tree[rs(p)];tree[p]%=mod;
    lazy_mul[p]=1;
}
void push_down(ll p,ll nl,ll nr){//懒惰标记 
    if(lazy_mul[p]!=1){
        lazy_mul[ls(p)]*=lazy_mul[p];lazy_mul[ls(p)]%=mod;
        lazy_mul[rs(p)]*=lazy_mul[p];lazy_mul[rs(p)]%=mod;
        lazy_add[ls(p)]*=lazy_mul[p];lazy_add[ls(p)]%=mod;
        lazy_add[rs(p)]*=lazy_mul[p];lazy_add[rs(p)]%=mod;
        tree[ls(p)]*=lazy_mul[p];tree[ls(p)]%=mod;
        tree[rs(p)]*=lazy_mul[p];tree[rs(p)]%=mod;
        lazy_mul[p]=1;
    }
    if(lazy_add[p]){
        ll mid=nl+((nr-nl)>>1);
        lazy_add[ls(p)]+=lazy_add[p];lazy_add[ls(p)]%=mod;
        lazy_add[rs(p)]+=lazy_add[p];lazy_add[rs(p)]%=mod;
        tree[ls(p)]+=(mid-nl+1)*lazy_add[p];tree[ls(p)]%=mod;
        tree[rs(p)]+=(nr-mid)*lazy_add[p];tree[rs(p)]%=mod;
        lazy_add[p]=0;
    }
}
void update_add(ll l,ll r,ll c,ll nl,ll nr,ll p){//区间修改加 
    if(l<=nl&&r>=nr){
        tree[p]+=(nr-nl+1)*c;tree[p]%=mod;
        lazy_add[p]+=c;lazy_add[p]%=mod;
        return;
    }
    ll mid=nl+((nr-nl)>>1);
    push_down(p,nl,nr);
    if(mid>=l) update_add(l,r,c,nl,mid,ls(p));
    if(r>mid) update_add(l,r,c,mid+1,nr,rs(p));
    tree[p]=tree[ls(p)]+tree[rs(p)];tree[p]%=mod;
}
void update_mul(ll l,ll r,ll c,ll nl,ll nr,ll p){//区间修改乘 
    if(l<=nl&&r>=nr){
        tree[p]*=c;tree[p]%=mod;
        lazy_add[p]*=c;lazy_add[p]%=mod;
        lazy_mul[p]*=c;lazy_mul[p]%=mod;
        return;
    }
    ll mid=nl+((nr-nl)>>1);
    push_down(p,nl,nr);
    if(mid>=l) update_mul(l,r,c,nl,mid,ls(p));
    if(r>mid) update_mul(l,r,c,mid+1,nr,rs(p));
    tree[p]=tree[ls(p)]+tree[rs(p)];tree[p]%=mod;
}
ll getsum(ll l,ll r,ll nl,ll nr,ll p){//区间求和 
    if(l<=nl&&r>=nr) return tree[p];
    ll mid=nl+((nr-nl)>>1),sum=0;
    push_down(p,nl,nr);
    if(mid>=l){sum+=getsum(l,r,nl,mid,ls(p));sum%=mod;}
    if(mid<r){sum+=getsum(l,r,mid+1,nr,rs(p));sum%=mod;}
    return sum%mod;
}
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m>>mod;
    for(int i=1;i<=n;i++){cin>>a[i];a[i]%=mod;}
    build(1,1,n); 
    int index,x,y,k; 
    for(int i=1;i<=m;i++){
        cin>>index;
        if(index==1){
            cin>>x>>y>>k;
            update_mul(x,y,k,1,n,1);
        }
        else if(index==2){
            cin>>x>>y>>k;
            update_add(x,y,k,1,n,1);
        }
        else if(index==3){
            cin>>x>>y;
            cout<<getsum(x,y,1,n,1)<<endl;
        }
    }
    return 0;
}

膜拜zhx

感谢zhx神奇的duantree

#include<bits/stdc++.h>
#define int long long
#define re register
#define il inline
#define lson nowl,mid,pos<<1
#define rson mid+1,nowr,pos<<1|1
#define maxn 100005
#define root 1,n,1
#define zhx 1000000007
#define pos_now nowl,nowr,pos
using namespace std;
int n,m,x,y,k,opt,a[maxn];
il int ls(int pos){return pos<<1;}
il int rs(int pos){return pos<<1|1;}
struct SegMent_Tree{
    int sum;
    int lazy;
    SegMent_Tree(){
        sum=lazy=0;
    }
}t[maxn<<2];
il SegMent_Tree operator+(const SegMent_Tree &ls,const SegMent_Tree &rs){
    SegMent_Tree temp;
    temp.sum=ls.sum+rs.sum;
    //temp.sum%=zhx;
    return temp;
}
il void build(int nowl,int nowr,int pos){//建树 
    if(nowl==nowr){
        t[pos].sum=a[nowl];
        return;
    }
    int mid=(nowl+nowr)>>1;
    build(lson);
    build(rson);
    t[pos]=t[ls(pos)]+t[rs(pos)];
}
il void revise(int nowl,int nowr,int pos,int plus){//修改 
    t[pos].sum+=(nowr-nowl+1)*plus;
    //t[pos].sum%=zhx;
    t[pos].lazy+=plus;
    //t[pos].lzay%=zhx;
}
il void push_down(int nowl,int nowr,int pos){//下放 
    if(t[pos].lazy){
        int mid=(nowl+nowr)>>1;
        revise(lson,t[pos].lazy);
        revise(rson,t[pos].lazy);
        t[pos].lazy=0;
    }
}
il void update(int l,int r,int nowl,int nowr,int pos,int plus){//更新 
    if(l<=nowl&&r>=nowr){
        revise(pos_now,plus);
        return;
    }
    int mid=(nowl+nowr)>>1;
    push_down(pos_now);
    if(l<=mid) update(l,r,lson,plus);
    if(r>mid) update(l,r,rson,plus);
    t[pos]=t[ls(pos)]+t[rs(pos)];
}
il SegMent_Tree query(int l,int r,int nowl,int nowr,int pos){
    if(l<=nowl&&r>=nowr){
        return t[pos];
    }
    int mid=(nowl+nowr)>>1;
    push_down(pos_now);
    SegMent_Tree temp;
    if(l<=mid) temp=temp+query(l,r,lson);
    if(r>mid) temp=temp+query(l,r,rson);
    return temp;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(re int i=1;i<=n;i++) cin>>a[i];
    build(root);
    while(m--){
        cin>>opt;
        if(opt==1){
            cin>>x>>y>>k;
            update(x,y,root,k);
        }
        if(opt==2){
            cin>>x>>y;
            cout<<query(x,y,root).sum<<endl;
        }
    }
    return 0;
}

KMP：

il int KMP(const string& a,const string& b){
    int la=a.size(),lb=b.size(),i=0,j=-1,sum=0;
    if(la<lb) return 0;
    kmp[i]=-1;
    while(i<lb){
        if(j==-1||b[i]==b[j]) kmp[++i]=++j;
        else j=kmp[j];
    }
    j=i=0;
    while(i<la){
        if(j==-1||b[j]==a[i]) ++i,++j;
        else j=kmp[j];
        if(j==lb){
            sum++;
            j=kmp[j-1];
            i--;
        }
    }
    return sum;
}