常用next[i][j]来表示从第i个位置开始，字符串j出现的第一个位置或其他含义
从而达到快速判断是否为模式串的(子序列)或者优化dp的目的

例题：
小Z的笔记 

#include <bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5 + 10;
char s[N];
char vis[26][26]; 
int nex[N][26];
int dp[N];
int main(){
    scanf("%d",&n);
    scanf("%s",s + 1);
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        char a,b;
        cin >> a >> b;
        vis[a-'a'][b-'a'] = vis[b-'a'][a-'a'] = 1;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++)
            nex[i][j] = nex[i-1][j];
        nex[i][s[i] - 'a'] = i;
    }
    for(int i=1;i<=n;i++){
        int p = s[i] - 'a';
        dp[i] = i;
        for(int j=0;j<26;j++){
            if(!vis[p][j]){
                int pos = nex[i-1][j];
                dp[i] = min(dp[i],i-pos-1+dp[pos]);
            }
        }
    }
    cout << dp[n] << endl;
    return 0;
}

计蒜客subsquence

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5+100;
const int INF = 0x3f3f3f3f;
char s[N];
char t[N];
struct sub_AM{
    int nxt[N][27];
    void init(char *s){
        int l=strlen(s);
        for(int i=0;i<26;i++) nxt[l][i]=INF;
        for(int i=l-1;i>=0;i--){
            for(int j=0;j<26;j++){
                nxt[i][j]=nxt[i+1][j];
            }
            nxt[i][s[i]-'a']=i;
        }
    }
    bool find(char *t){
        int pos=-1;
        int l=strlen(t);
        for(int i=0;i<l;i++){
            pos=nxt[pos+1][t[i]-'a'];
            if(pos==INF) return 0;
        }
        return 1;
    }
}solve;
int main(){
    scanf("%s",s);
    solve.init(s);
    int q;
    scanf("%d",&q);
    while(q--){
        scanf("%s",t);
        if(solve.find(t)){
            puts("YES");
        }
        else puts("NO");
    }        
    return 0;
}

当然正着和反着皆可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
char s[N];
char t[N];
int nex[N][26];
int n,len;
void solve(){
    for(int i=n+1,j=len;j>=1;j--){
        i = nex[i-1][t[j] - 'a'];
        if(i == 0){
            puts("NO");
            return;
        }
    } 
    puts("YES"); 
}
int main(){
    scanf("%s",s + 1);
    n = strlen(s + 1);
    //printf("%s\n",s + 1);
    for(int i=1;i<=n;i++){
        for(int j=0;j<26;j++)
            nex[i][j] = nex[i-1][j];
        nex[i][s[i] - 'a'] = i; 
    }
    int m;
    cin >> m;
    while(m--){
        scanf("%s",t + 1);
        len = strlen(t + 1);
        //printf("%s\n",t + 1);
        solve();
    }
    return 0;
}

以下参考了青烟大佬的题解
hdu6586

题意：需要找到一个字典序最小的长度为k的满足
且a~z的第i个字符出现次数必须在[,]之间
思路：
预处理记录下每个位置后面每个字符的数量，和每个字符的位置，这里我们就通过位置关系，枚举字符来判断要这个字符是否符合条件，l和r记录该字符还需要多少个，记录两个值

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int nex[N][26],sum[N][26],n,k,ok,pos,cnt[26],cl[26],cr[26]; char str[N],res[N];
inline int check(int p,int ch){
    int now=nex[pos][ch],nd=k-p-1,num=0,num1=0;
    if(now>n||cnt[ch]>=cr[ch])    return 0;
    for(int i=0;i<26;i++){
        if(cnt[i]+sum[now+1][i]+(i==ch)<cl[i])    return 0;
        if(cl[i]>cnt[i]+(ch==i))    num1+=cl[i]-cnt[i]-(ch==i);
        num+=cr[i]-cnt[i]-(i==ch);
    }
    return num>=nd&&num1<=nd;
}
inline void solve(){
    n=strlen(str+1); ok=1; pos=1; res[k+1]='\0';
    for(int i=0;i<26;i++)    scanf("%d %d",&cl[i],&cr[i]);
    for(int i=0;i<26;i++)    sum[n+1][i]=0,nex[n+1][i]=n+1,cnt[i]=0;
    for(int i=n;i>=1;i--){
        for(int j=0;j<26;j++)    sum[i][j]=sum[i+1][j],nex[i][j]=nex[i+1][j];
        sum[i][str[i]-'a']++,nex[i][str[i]-'a']=i;
    }
    for(int i=1;i<=k&&ok;i++){
        int flag=0;
        for(int j=0;j<26;j++)    if(check(i-1,j)){
            res[i]=j+'a'; flag=1; cnt[j]++; pos=nex[pos][j]+1;    break;
        }
        if(!flag)    ok=0;
    }
    if(!ok)    puts("-1");
    else    printf("%s\n",res+1);
}
signed main(){
    while(~scanf("%s %d",str+1,&k))    solve();
    return 0;
}