牛客多校三

H (SAM,线段树)

题意:有一个母串,和一堆串,串每个位置有代价,现在问你这些串的子串恰好为母串的子串的最大权值

解:子串问题肯定会想到SAM,我只需要给母串建立一个SAM,然后子串上去跑匹配,但是匹配的长度需要另外的计算,每次看着失配之后,需要跳父亲边,知道能匹配,匹配之后,长度因该len[fa]+1,就ok了,至于如何求值,只需要在线段树上求出前缀和数组,然后区间求最小值就好了,灰常简单,就完结撒花了

#include<bits/stdc++.h>
#define int long long
using namespace std;
 
const int N=400005;
 
int n,m,k;
string s,h;
 
//�����Զ����ĸ��ڵ���1 
 
int tot=1,pre=1,ch[N][26],len[N],fa[N],siz[N];
 
void ins(int c) {
    int now=++tot, p=pre; pre=now; siz[now]++;
    len[now]=len[p]+1;
    for(;!ch[p][c] && p;p=fa[p]) ch[p][c]=now;
    if(!p) return (void)(fa[now]=1);
    int q=ch[p][c];
    if(len[q] == len[p] + 1) return (void)(fa[now]=q);
    int tt=++tot;
    len[tt] = len[p]+1; 
    for(int i=0;i<26;i++) ch[tt][i]=ch[q][i];
    fa[tt]=fa[q], fa[now]=fa[q]=tt;
    for(;ch[p][c] == q && p;p=fa[p]) ch[p][c]=tt;
}
 
int val[N];
 
//ÿ�εõ�һ�� �����Ҷ˵�̶�,��˵���ƶ������һ�� 
int mi[N<<2];
 
#define ls (now<<1)
#define rs ((now<<1)|1)
#define mid ((l+r)>>1)
 
void bulit(int now,int l,int r) {
    if(l==r) return (void)(mi[now]=val[l]);
    bulit(ls,l,mid);
    bulit(rs,mid+1,r);
    mi[now] = min(mi[ls],mi[rs]);
}
 
int get_mi(int now,int l,int r,int x,int y) {
    if(x>y) return (1ll<<60);
    if(x<=l && r<=y) {
        return mi[now];
    }
    int tmp=1e18;
    if(x<=mid) tmp=min(tmp,get_mi(ls,l,mid,x,y));
    if(y>mid) tmp=min(tmp,get_mi(rs,mid+1,r,x,y));
    return tmp;
}
 
void get() {
    int ans=0; int l=0;
    int now=1;
    for(int i=0;i<h.size();i++) {
        while(now!=1 && (ch[now][h[i]-'a']<=1)) {
            now=fa[now]; l=len[now];
        }
//		cout<<now<<endl;
        if(ch[now][h[i]-'a']>1) now=ch[now][h[i]-'a'],l++;
         
//      cout<<len[now]<<endl;
		if(l) {
	        int tmp=val[i+1]-get_mi(1,0,m,max(i-l+1,0ll),i+1);
	        ans=max(ans,tmp);   			
		}

    }
    cout<<ans<<endl;
     
}
 
 
signed main() {
    ios::sync_with_stdio(0);
    cin>>n>>m>>k;
    cin>>s;
    for(int i=0;i<s.size();i++) ins(s[i]-'a');
    for(int i=1;i<=m;i++) cin>>val[i],val[i]+=val[i-1];
    bulit(1,0,m);
    for(int i=1;i<=k;i++) {
        cin>>h;
        get();
    }
     
     
     
}