Codeforces - 1203D2 - Remove the Substring (hard version)

https://codeforces.com/contest/1203/problem/D2

上次学了双指针求两个字符串之间的是否t是s的子序列。但其实这个双指针可以求出的是s的前i个位置中匹配t的最长的前缀。反过来求一次可以得到最长的后缀。

然后怎么找要删除的位置呢？暴力n^2肯定可以，然后线性写挂到自闭。

枚举位置[i,j)，注意j可以取相等，所以预处理前后缀的时候把n位置的后缀也算好。

去除子串[i,j)，那么剩下的就是[0,i-1]和[j,n-1]两个子串，他们匹配的长度加起来超过tl就是合法。

#include<bits/stdc++.h>

using namespace std;

int dpprefix[200005];

int dpsuffix[200005];

char s[200005], t[200005];

int sl, tl;

void prefix() {

    int i = 0, j = 0;

    while(i < sl || j < tl) {

        if(i < sl && j < tl) {

            if(s[i] == t[j]) {

                dpprefix[i] = j + 1;

                ++i, ++j;

            } else {

                dpprefix[i] = j;

                ++i;

            }

        } else if(j == tl) {

            dpprefix[i] = tl;

            ++i;

        } else if(i == sl) {

            dpprefix[i] = j;

            break;

        }

    }

}

void suffix() {

    int i = sl - 1, j = tl - 1;

    while(i >= 0 || j >= 0) {

        if(i >= 0 && j >= 0) {

            if(s[i] == t[j]) {

                dpsuffix[i] = tl - j;

                --i, --j;

            } else {

                dpsuffix[i] = tl - (j + 1);

                --i;

            }

        }  else if(j < 0) {

            dpsuffix[i] = tl;

            --i;

        } else if(i < 0) {

            dpprefix[i] = tl - j;

            break;

        }

    }

}

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    while(~scanf("%s%s", s, t)) {

        memset(dpprefix, 0, sizeof(dpprefix));

        memset(dpsuffix, 0, sizeof(dpsuffix));

        sl = strlen(s), tl = strlen(t);

        prefix();

        suffix();

        int i = 0, j = 1;

        int ans = 0;

        while(i < sl || j <= sl) {

            if(i == 0) {

                while(j <= sl && dpsuffix[j] >= tl) {

                    ans = max(ans, j - i);

                    ++j;

                }

            } else {

                while(j <= sl && dpprefix[i - 1] + dpsuffix[j ] >= tl) {

                    ans = max(ans, j - i);

                    ++j;

                }

            }

            ++i;

        }

        printf("%d\n", ans);

    }

    return 0;

}

巴特西

Codeforces - 1203D2 - Remove the Substring (hard version) - 双指针

最新文章

热门文章