[문제풀이] CF808G Anthem of Berland

제목의 뜻

전송문luogu

문제풀이

dp와 kmp의 교묘한 결합.
텍스트 문자열 s의 길이를 nnn, 모드 문자열 t의 길이를 mmm로 설정합니다.문제면에서 nm≤107nm\leq10^7nm≤107을 적나라하게 알려주면 복잡도는 O(nm)O(nm)O(nm)급이어야 한다는 것을 알 수 있다. 이 nn의 복잡도는 s를 한 번 훑어보는 것이 틀림없다. mmm는 s의 모든 위치에 대해 폭력적인 일치로 추측할 수 있다.
우리는 dp로 이 문제를 해결하는 것을 고려할 수 있다.fi f 설정ifi는 t가 s의 전 ii i 개 위치에서 가장 큰 출현 횟수를 나타낸다.그러면 만약에 한 위치가 이전의 위치에서 옮겨오려면 t가 이 위치에서 s와 일치하는 것을 만족시켜야 한다. 이 부분은 O(m)O(m)O(m)폭력적으로 판단할 수 있다.
구체적으로 어떻게 옮길까요?일단 분명히 fi -3 m f{i-m} fi -3 m가 옮겨오면 i -3 m + 1 ∼ i i-m +1\sim i -3 m +1 ∼i 이 부분에 온전한 t를 넣는다는 뜻이다.
그러나 이것은 부족하다. 왜냐하면 이 위치 이전에 연속적으로 여러 개의 t를 중첩적으로 놓았을 수도 있기 때문이다. 이것은 새로 넣은 이 t가 완전하지 않고 이전 t의 접미사와 중첩되어 구성된 것을 의미한다.그러면 이것은 t의 접두사와 접두사가 같다는 것을 만족시켜야 한다.
이것은 우리로 하여금 kmp 알고리즘 중의next 수조를 생각하게 했다.우리는 m에서부터 넥스트를 계속 추어 접두사와 접두사가 같다는 것을 보장할 수 있다.
그러나 또 하나의 문제가 있다. 만약에 우리가 현재 길이가 kkk의 앞뒤 접미사가 같다고 가정하면 우리는 fi-3(m-3k)f 에서 직접{i-(m-k)}fi-3(m-3-k)이전, fff의 정의가 fi-3-(m-3k)f 를 보장하지 않기 때문에{i-(m-k)}fi-3(m-3k)이라는 자리에 t를 넣었을 거야.
그래서 저희가 gi g 을 하나 더 정의할게요.i gi는 s의 전 i i i 위치를 표시하고 마지막으로 t의 최대 출현 횟수를 강제로 넣는다.그러면 이렇게 하면 우리 위의 상황은 ggg 간의 이동을 통해 실현할 수 있다.즉 g i = max {g i -3 (m -3 k) + 1, g i} gi=\max\{g_{i-(m-k)}+1,g_i\} gi=max {gi-3 (m -3 k) +1,gi},next 업데이트를 계속 누르면 됩니다.
g g g g 를 옮긴 후, fi = max\{f i - 1, g i} f 를 다시 명령합니다.i=\max\{f_{i-1}, g_i\} fi=max {fi -3 1,gi}, 즉 t를 넣는 것과 안 넣는 두 가지 상황을 고려한 것이다.

코드

#include 
#define MAX 100005
using namespace std;

char s[MAX], t[MAX];
int n, m;
int Next[MAX], f[MAX], g[MAX];

bool chk(int p){
    for(int j = 1; j <= m; j++){
        if(s[p-j+1] != t[m-j+1] && s[p-j+1] != '?') return false;
    }
    return true;
}

int main()
{
    scanf("%s%s", s+1, t+1);
    n = strlen(s+1), m = strlen(t+1);
    for(int i = 2, j = 0; i <= m; i++){
        while(j && t[j+1] != t[i]) j = Next[j];
        if(t[j+1] == t[i]) j++;
        Next[i] = j;
    }

    for(int i = 1; i <= n; i++){
        f[i] = f[i-1];
        if(chk(i)){
            g[i] = f[i-m]+1;
            for(int j = Next[m]; j; j = Next[j]){
                g[i] = max(g[i], g[i-(m-j)]+1);
            }
            f[i] = max(f[i], g[i]);
        }
    }
    cout << f[n] << endl;

    return 0;
}