题目链接：https://codeforces.com/contest/1163/problem/D
题目大意：
首先定义f(s,t)函数，表示t中含有s串个数
之后首先给出一个c串，由'*'和小写字母组成，其中'*'可以替换为26个字母中的任意一个
之后给出两个串s,t。
要求你根据c串中的'*'构造c串使得f(s,c) - f(t,c)最大
题目思路：
多字符串包含关系必然会想到AC自动机
首先考虑，建立AC自动机时，节点得权值情况
在字典树上s的终结点权值为1，t的终结点权值为-1
之后每个节点的权值呢?
就是fail树的前缀和，理解很容易当前串会包含fail树的前缀，只要包含这个前缀就会产生贡献
之后进行dp就可以了
由于s和t的长度都很小，所以AC自动机的节点也超不过100个
所以我们可以想到n*node*26的dp方案
首先枚举第i个字母，前驱是第k个节点，当前节点选择j
具体转移在注释：
for(int i=1;i<=len;i++){for(int k=0;k<nNode;k++){///上一个节点是kif(dp[i-1][k] == -INF) continue;if(p[i] == '*'){for(int j=0;j<26;j++){///当前匹配字符int temp = k;while(~temp&&t[temp][j] == 0) temp = fail[temp];///找到可以有贡献的第一个节点if(temp == -1) dp[i][0] = max(dp[i][0],dp[i-1][k]);else{int op = t[temp][j];///虽然找到了前缀匹配但是还是需要从dp[i-1][k]转移过来dp[i][op] = max(dp[i][op],dp[i-1][k]+val[op]+val[fail[op]]);///由于此时只有两个串直接算即可}}}else{///只能单独选择int temp = k;while(~temp&&t[temp][p[i]-'a'] == 0) temp = fail[temp];if(temp == -1) dp[i][0] = max(dp[i][0],dp[i-1][k]);else{int op = t[temp][p[i]-'a'];dp[i][op] = max(dp[i][op],dp[i-1][k]+val[op]+val[fail[op]]);}}}}
变式：
理解上述问题之后，这个问题还可以做一个变式，首先给出n个字符串，并且给出每个字符串的出现一次的权值，让你构造一个长度为m的字符串，使得这个字符串的权值最小,唯一不同就是需要预处理一下匹配到j节点时会产生的权值
Code：
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int Maxn=2e7+10;
const int maxn =1e3+10;
const int mod=1e9+9;
const int Mod = 1e9+7;
///const double eps=1e-10;
inline bool read(ll &num)
{char in;bool IsN=false;in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
struct Aho{ll nNode=0;int t[maxn][26];///tire树int val[maxn];int fail[maxn];///fail指针int id[maxn];ll dp[maxn][105];///当前第i个字符匹配到j节点产生的最大值void _inint_(){nNode = 1;}int newNode(){for(int i=0; i<26; ++i) t[nNode][i]=0;val[nNode]=0;return nNode++;}void Insert(char *p,int f){///tire的插入int len=strlen(p);int rt=0;for(int i=0;i<len;i++){int x=p[i]-'a';if(!t[rt][x]) t[rt][x]=newNode();rt=t[rt][x];}val[rt] = f;}void build(){///fail树的建立queue<int>q;fail[0]=-1;///初始点设为-1 无failq.push(0);int cnt = 0;while(!q.empty()){int u=q.front();q.pop();for(int i=0;i<26;i++){if(t[u][i]){id[++cnt] = t[u][i];if(u==0) fail[t[u][i]]=0;else{int v=fail[u];while(~v){if(t[v][i]){fail[t[u][i]]=t[v][i];break;}v=fail[v];}if(v==-1) fail[t[u][i]]=0;}q.push(t[u][i]);}}}}ll Match(char *p){int len = strlen(p+1);for(int i=0;i<=len;i++)for(int k=0;k<nNode;k++)dp[i][k]=-INF;dp[0][0] = 0;for(int i=1;i<=len;i++){for(int k=0;k<nNode;k++){///上一个节点是kif(dp[i-1][k] == -INF) continue;if(p[i] == '*'){for(int j=0;j<26;j++){///当前匹配字符int temp = k;while(~temp&&t[temp][j] == 0) temp = fail[temp];///找到可以有贡献的第一个节点if(temp == -1) dp[i][0] = max(dp[i][0],dp[i-1][k]);else{int op = t[temp][j];///虽然找到了前缀匹配但是还是需要从dp[i-1][k]转移过来dp[i][op] = max(dp[i][op],dp[i-1][k]+val[op]+val[fail[op]]);///由于此时只有两个串直接算即可}}}else{///只能单独选择int temp = k;while(~temp&&t[temp][p[i]-'a'] == 0) temp = fail[temp];if(temp == -1) dp[i][0] = max(dp[i][0],dp[i-1][k]);else{int op = t[temp][p[i]-'a'];dp[i][op] = max(dp[i][op],dp[i-1][k]+val[op]+val[fail[op]]);}}}}ll maxl = -INF;for(int k=0;k<nNode;k++) maxl = max(maxl,dp[len][k]);return maxl;}
}aho;
char s[maxn],t[maxn];
int main()
{scanf("%s",t+1);aho._inint_();scanf("%s",s);aho.Insert(s,1);scanf("%s",s);aho.Insert(s,-1);aho.build();printf("%lld\n",aho.Match(t));return 0;
}
/**
****ab****
abcd
cdab
**/