POJ 1936 DP

题意

传送门 POJ 1936

题解

$dp[i]$ 代表字符串 $t$ 的区间 $[0,i]$ 可以匹配的 $s$ 的最大长度

$dp[i]=\begin{cases} dp[i-1]+1 & t[i]=s[dp[i-1]]\\ dp[i-1] & otherwise\\ \end{cases}$

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
using namespace std;
#define inf 0x3f3f3f3f
#define maxn 100005
char s[maxn], t[maxn];
int dp[maxn];

int main()
{
    while (~scanf(" %s %s", s, t))
    {
        memset(dp, 0, sizeof(dp));
        int n1 = strlen(s), n2 = strlen(t);
        if (n1 > n2)
        {
            puts("No");
            break;
        }
        bool f = 0;
        for (int i = 0; i < n2; i++)
        {
            dp[i] = (i == 0 ? 0 : dp[i - 1]) + (t[i] == s[dp[i - 1]] ? 1 : 0);
            if (dp[i] == n1)
            {
                f = 1;
                break;
            }
        }
        puts(f ? "Yes" : "No");
    }
    return 0;
}

本文地址：https://blog.csdn.net/neweryyy/article/details/107344734