POJ 1936 All in All
PCK参加しました。
bitDP気づいたけど実装力なさすぎでバグりまくったのが悔しい
本選参加できるかどうか微妙(地域枠)
今はコード手元にないから今度のせる
(追記) コードはどっかいった
部分文字列かどうか判定する問題
再帰書くだけでよい
solve(p, q) はsのp文字目とtのq文字目が同じかどうかみていく感じ
同じだったら solve(p+1, q+1)
違ったら solve(p, q+1)
の結果が答え
#include <cstdio> #include <cstring> using namespace std; const int L = 100000; char S[L]; char T[L]; int slen, tlen; int solve(int p, int q){ if(slen <= p || tlen <= q) return 0; if(S[p] == T[q]){ if(p == slen-1) return 1; return solve(p+1, q+1); } return solve(p, q+1); } int main(){ char c; while(scanf("%s", S) != EOF){ scanf("%c", &c); scanf("%s", T); scanf("%c", &c); slen = strlen(S); tlen = strlen(T); printf("%s\n", solve(0,0)?"Yes":"No"); } return 0; }