当前位置： 移动技术网 > IT编程>开发语言>JavaScript > POJ 1936 DP

POJ 1936 DP

2020年07月15日  | 移动技术网IT编程  | 我要评论
题意传送门 POJ 1936题解dp[i]dp[i]dp[i] 代表字符串 ttt 的区间 [0,i][0,i][0,i] 可以匹配的 sss 的最大长度dp[i]={dp[i−1]+1t[i]=s[dp[i−1]]dp[i−1]otherwisedp[i]=\begin{cases}dp[i-1]+1 & t[i]=s[dp[i-1]]\\dp[i-1] & otherwise\\\end{cases}dp[i]={dp[i−1]+1dp[i−1]​t[i]=s[dp[i−1
题意

传送门

题解

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

dp[i]={dp[i−1]+1t[i]=s[dp[i−1]]dp[i−1]otherwisedp[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

您可能感兴趣的文章:

如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网