CF808G

发表于 分类于
Anthem of Berland

Anthem of Berland

怎么说呢，这里带问号的匹配情况很复杂，直接 $O(nm)$ 爆搞 DP，就是直接枚举之前状态是对的，按照 KMP 就错了（因为很有可能会对应多种情况而 $nxt$ 考虑不到。。。）。

一个常规的设计，定义 $f(i,j)$ 表示匹配了前 $i$ 位，最后又匹配了 $j$ 位的最大的匹配数。

很显然一般情况，当 $s_i=t_j$ 或 $t_j=\texttt{?}$ 的时候，$f(i,j)=f(i-1,j-1)$。

在 $f(i-1,m-1)$ 存在的时候，且我们又匹配了 $s_i$ 与 $t_m$，这个时候说明我们匹配出一个完整的模式串，直接让 $f(i,m)\leftarrow f(i,m)+1$。

在我们的 $f(i,m)$ 有意义的情况下，显然它的公共前缀后缀都可以取这个答案，我们总和一下取个最大即可。

简单来说，就是 $k$ 从 $m$ 不断跳 $nxt$，然后 $f(i,k)=\max\{f(i,k),f(i,m)\}$。

最后 $f(i,0)$ 舍弃了一切，把前面状态中的最大值赋给它就好了。

最后我们的答案就是 $f(n,0)$。

为了方便，我们直接把除 $f(0,0)$ 外的状态赋 $-\infty$，这样就不需要管是否有意义了，没有意义直接就是 $-\infty$。

然后节省空间开个滚动数组。

时间复杂度 $O(nm)$。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
namespace Ehnaev{
  inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
    while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
    return ret*f;
  }
  inline void write(ll x) {
    static char buf[22];static ll len=-1;
    if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
    else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
    while(len>=0) putchar(buf[len--]);
  }
}using Ehnaev::read;using Ehnaev::write;

const ll N=1e5,inf=(1ll<<31)-1;

ll f[2][N+5],nxt[N+5];
char s[N+5],t[N+5];

inline void KMP_Pre(char *s,ll len) {
  for(ll i=2;i<=len;i++) {
    ll j=nxt[i];
    while(j&&s[j+1]!=s[i]) j=nxt[j+1];
    j+=(s[j+1]==s[i]);nxt[i+1]=j;
  }
}

inline void KMP(char *s,char *t,ll len1,ll len2) {
  for(ll k=1;k<=len2;k++) f[0][k]=-inf;
  for(ll i=1;i<=len1;i++) {
    for(ll k=0;k<=len2;k++) f[i&1][k]=-inf;
    for(ll k=1;k<=len2;k++) {
      if(s[i]==t[k]||s[i]=='?') f[i&1][k]=f[(i-1)&1][k-1];
      if(k==len2) f[i&1][k]++;
    }
    ll k=nxt[len2+1];
    while(1) {
      f[i&1][k]=max(f[i&1][k],f[i&1][len2]);
      k=nxt[k+1];if(k==0) break;
    }
    for(ll k=0;k<=len2;k++) {
      f[i&1][0]=max(f[i&1][0],max(f[i&1][k],f[(i-1)&1][k]));
    }
  }
}

int main() {

  scanf("%s",s+1);ll n=strlen(s+1);
  scanf("%s",t+1);ll m=strlen(t+1);
  KMP_Pre(t,m);

  KMP(s,t,n,m);

  write(f[n&1][0]);

  return 0;
}