# 7A Điền xâu

Ta sẽ điền cho từng vị trí $1,2..n$.

Nhận thấy : Để tạo thành xâu $T$, thì ta cần phải tạo thành các tiền tố độ dài $1,2..|T|$.

Gọi $dp[i][j]$ là số lần xâu $T$ xuất hiện nhiều nhất khi ta đã điền tới kí tự thứ $i$ và đoạn $[i-j+1..j]$ là $1$ tiền tố của xâu $T$.

Vậy khi điền tới $i$, ta cần biết nếu ta điền ở vị trí $i+1$ $1$ kí tự $j$ nào đó, thì độ dài tiền tố lớn nhất trong xâu $T$ mà ta đã tạo được tới $i+1$ là bao nhiêu.

Vậy ta cần quản lý thông tin này trong một mảng $next[i][j]$.

Ta sẽ xây mảng $next$ như sau :
- Nếu $T[i+1] = j$ thì $next[i][j] = i +1$.
- Nếu không thì $next[i][j] = next[KMP[i]][j]$. Ở đây $KMP[i]$ chính là $max(i-j)$ với mọi $j > 1$ sao cho $T[j..i]$ là $1$ tiền tố của $T$. Ta có thể tính được bằng cách dùng thuật toán KMP hoặc Zfuction (ở đây tác giả sử dụng Zfunction).

Ta có : $dp[next[j][a[i+1]]][j] = max (dp[next[j][a[i+1]]][j], dp[i][j] + (next[j][a[i+1]] == n))$

Đáp án chính là $max(dp[n][i])$ với $(i \le |T|)$.

:::spoiler Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define sc second
#define pll pair<ll,ll>
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define TASK "main"
const int nmax = 1e5 + 7;
int f[nmax][26];
vector<int> dp[nmax];
int z[nmax];
vector<int> toer[nmax];
int g[nmax];
string s;
string t;
void solve(){
    cin >> s >> t;
    int l = 0,r = 0;
    z[0] = 1;
    for(int i = 1 ;i<t.size();++i){
        z[i] = min(z[i-l], r-i +1);
        r=max(r,i);
        if(t[i] == t[0]) z[i] = max(z[i], 1);
        while(i + z[i] -1 ==r && i + z[i] - 1  < t.size() && t[i+z[i]] == t[z[i]]){
            ++z[i];
            ++r;
            l= i;
        }
    }
    set<int> se;
    for(int i =0;i<t.size();++i){
        se.insert(i);

        toer[i+z[i]].push_back(i);
        for(auto x: toer[i]){
            se.erase(se.find(x));
        }
        if(se.size()){
            g[i] = i - *se.begin() + 1;
        }
    }
    for(int i = 0 ;i<=s.size();++i){
        dp[i].resize(t.size() + 3,-1);
    }
    dp[0][0] = 0;
    if(t[0] == s[0] || s[0] == '?') dp[0][1] = 1 == t.size();
    // for(int i =0;i<t.size();++i) cout << g[i] << ' ';
    int ans = 0;
    for(int i = 0;i<s.size() ;++i){
        for(int j = t.size();j>=0;--j){
            if(dp[i][j] == -1) continue;
            if(j>0)
            dp[i][g[j-1]] = max(dp[i][g[j-1]],dp[i][j]);
            ans = max(ans, dp[i][j]);
            if(s[i+1] == '?'){
                for(int c = 0;c<26;++c){
                    if((char)('a' + c) == t[j]){
                        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + (j+1 == t.size()));
                    } else dp[i+1][0] = max(dp[i+1][0],dp[i][j]);
                }
            } else {
                if(s[i+1] == t[j]){
                    dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + (j+1 == t.size()));
                } else dp[i+1][0] = max(dp[i+1][0],dp[i][j]);
            }
            dp[i][0] = max(dp[i][0], dp[i][j]);
        }
    } 
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    if(fopen(TASK ".inp","r")){
    freopen(TASK ".inp","r",stdin);
    freopen(TASK ".out","w",stdout);
    }
    solve();
}


 

:::