题目链接
设 \(f _ {i, j}\) 为 \(s\) 的扫了前 \(i\) 个字符，匹配到 \(t _ j\) 的 LCS 长度。转移：\(f _ {i, j} \leftarrow f _ {i - 1, j}\)，\(f _ {i, j} \leftarrow f _ {i - 1, k} + 1\)（\(k < j\)，\(s _ i = t _ j\)）。
观察到 \(0 \le f _ {i, j + 1} - f _ {i, j} \le 1\)，考虑维护 \(f _ i\) 的差分序列 \(F _ i\)。记 \(G _ c\) 为字符 \(c\) 在 \(t\) 中的分布位置。
接下来需要一些对结构的观察。举个例子：
你发现若把 \(F _ {i - 1}\) 按 \(\ldots \texttt {0001}\) 的结构分成若干段（最后一段为 \(\texttt {0000} \ldots\)），则每一段为 \(F _ {i - 1} \operatorname{|} G _ {s _ i}\) 的 lowbit，即上述例子 \(F _ i = \underline{\texttt{010}} \space \underline{\texttt{01}} \space \underline{\texttt{1}} \space \underline{\texttt{1}} \space \underline{\texttt{0100}} \space \underline{\texttt{10}}\)。
那么这个东西用位运算怎么做？
考虑类比 lowbit(x)=x^(x&(x-1))，记 \(h = F _ {i - 1} \operatorname {|} G _ {s _ i}\)，则 F[i]=h^(h&(h-(F[i-1]<<1|1)))。
这是因为 F[i-1]<<1|1 相当于每一段的最低位都有 1，又因为 \(h\) 的每一段都至少有一个 1（除了最后一段），故每一段做 lowbit 操作互不影响。
至此，可以手写 bitset 维护，并需要额外实现减法。
上代码：
#include<cstdio>
#include<cstring>
#define N 50005
using namespace std;template<const int L> struct Bitset {#define o inline#define pc __builtin_popcountlltypedef unsigned long long ull;static const int len=(L>>6)+1;ull a[len];o void reset() {memset(a,0,sizeof(a));}o Bitset() {reset();}o ull &operator[](int x) {return a[x];}o bool get(int x) {return a[x>>6]>>(x&63)&1;}o void set(int x,bool c) {if((a[x>>6]&1ull<<(x&63))!=c) a[x>>6]^=1ull<<(x&63);}o friend Bitset operator&(Bitset a,Bitset b) {for(int i=0;i<len;i++) a[i]=a[i]&b[i];return a;}o friend Bitset operator|(Bitset a,Bitset b) {for(int i=0;i<len;i++) a[i]=a[i]|b[i];return a;}o friend Bitset operator^(Bitset a,Bitset b) {for(int i=0;i<len;i++) a[i]=a[i]^b[i];return a;}o friend Bitset operator<<(Bitset a,int k) {int u=k>>6,v=k&63,w=64-k;ull st=w<64?(1ull<<w)-1:-1ull; Bitset b;for(int i=0;i<len;i++) {if(i-u>=0) b[i]|=(a[i-u]&st)<<v;if(i-u-1>=0) b[i]|=a[i-u-1]>>w;}return b;}o friend Bitset operator-(Bitset a,Bitset b) {bool t=0;for(int i=0;i<len;i++) {bool r=a[i]<b[i]||t&&a[i]==b[i];a[i]-=b[i]+t,t=r;}return a;}o int count() {int res=0;for(int i=0;i<len;i++) res+=pc(a[i]);return res;}
};
int n,m;
char s[N],t[N];
Bitset<N> f,g,h,p[26];
int main() {scanf("%s%s",s+1,t+1),n=strlen(s+1),m=strlen(t+1);for(int i=1;i<=m;i++) p[t[i]-'a'].set(i,1);for(int i=1;i<=n;i++) {g=f|p[s[i]-'a'],h=f<<1,h.set(0,1);f=g^g&(g-h);}printf("%d\n",f.count());return 0;
}