{"id":161,"date":"2026-05-16T11:24:31","date_gmt":"2026-05-16T03:24:31","guid":{"rendered":"https:\/\/huxiaole.cloud\/?p=161"},"modified":"2026-05-20T18:27:06","modified_gmt":"2026-05-20T10:27:06","slug":"at_abc452_d-abc452d-no-subsequence-substring","status":"publish","type":"post","link":"https:\/\/huxiaole.cloud\/index.php\/2026\/05\/16\/at_abc452_d-abc452d-no-subsequence-substring\/","title":{"rendered":"AT_abc452_d ABC452D No-Subsequence Substring"},"content":{"rendered":"\n<h1 class=\"wp-block-heading\">AT_abc452_d [ABC452D] No-Subsequence Substring<\/h1>\n\n\n\n<h2 class=\"wp-block-heading\">\u9898\u76ee\u63cf\u8ff0<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u7ed9\u5b9a\u7531\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210\u7684\u5b57\u7b26\u4e32 S \u548c T\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6c42 S \u7684\u6240\u6709\u975e\u7a7a\u5b50\u4e32\u4e2d\uff0c\u4e0d\u5305\u542b T \u4f5c\u4e3a\uff08\u4e0d\u4e00\u5b9a\u8fde\u7eed\u7684\uff09\u5b50\u5e8f\u5217\u7684\u5b50\u4e32\u4e2a\u6570\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u8fd9\u91cc\uff0cS \u7684\u4e24\u4e2a\u5b50\u4e32\u53ea\u8981\u53d6\u51fa\u7684\u4f4d\u7f6e\u4e0d\u540c\uff0c\u5373\u4f7f\u5b57\u7b26\u4e32\u5185\u5bb9\u76f8\u540c\u4e5f\u89c6\u4e3a\u4e0d\u540c\u5b50\u4e32\u3002<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">\u5b50\u4e32\uff1a\u5b57\u7b26\u4e32 X \u7684\u5b50\u4e32\u662f\u6307\u4ece X \u5f00\u5934\u5220\u9664 0 \u4e2a\u4ee5\u4e0a\u5b57\u7b26\u3001\u4ece\u672b\u5c3e\u5220\u9664 0 \u4e2a\u4ee5\u4e0a\u5b57\u7b26\u540e\u5f97\u5230\u7684\u5b57\u7b26\u4e32\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u5b50\u5e8f\u5217\uff1a\u5b57\u7b26\u4e32 X \u7684\u5b50\u5e8f\u5217\u662f\u6307\u4ece X \u4e2d\u5220\u9664 0 \u4e2a\u4ee5\u4e0a\u5143\u7d20\u540e\uff0c\u5269\u4f59\u5143\u7d20\u6309\u539f\u987a\u5e8f\u6392\u5217\u5f97\u5230\u7684\u5b57\u7b26\u4e32\u3002<\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u8f93\u5165\u4ece\u6807\u51c6\u8f93\u5165\u4ee5\u4ee5\u4e0b\u683c\u5f0f\u7ed9\u51fa\uff1a<\/p>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p class=\"wp-block-paragraph\">S T<\/p>\n<\/blockquote>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u51fa\u683c\u5f0f<\/h2>\n\n\n\n<p class=\"wp-block-paragraph\">\u4e00\u884c\uff0c\u8f93\u51fa\u7b54\u6848\u3002<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #1<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #1<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>abrakadabra\naba\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #1<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>51\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #2<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #2<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>aaaaa\na\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #2<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>0\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8f93\u5165\u8f93\u51fa\u6837\u4f8b #3<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u5165 #3<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>rdddrdtdcdrrdcredctdordoeecrotet\ndcre\n<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\">\u8f93\u51fa #3<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code>263\n<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">\u8bf4\u660e\/\u63d0\u793a<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\">\u6837\u4f8b\u89e3\u91ca 1<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">\u4f8b\u5982\uff0cS \u7684\u7b2c 1 \u4e2a\u5b57\u7b26\u5230\u7b2c 3 \u4e2a\u5b57\u7b26\u7ec4\u6210\u7684\u5b50\u4e32 <code>abr<\/code> \u4e0d\u5305\u542b T \u4f5c\u4e3a\u5b50\u5e8f\u5217\u3002\u6b64\u5916\uff0c<code>k<\/code>\uff08\u4ec5 S \u7684\u7b2c 5 \u4e2a\u5b57\u7b26\uff09\u548c <code>akada<\/code>\uff08S \u7684\u7b2c 4 \u4e2a\u5b57\u7b26\u5230\u7b2c 8 \u4e2a\u5b57\u7b26\uff09\u7b49\u5171 51 \u4e2a\u5b50\u4e32\u6ee1\u8db3\u6761\u4ef6\u3002<\/p>\n\n\n\n<p class=\"wp-block-paragraph\">\u6ce8\u610f\uff1a<code>abr<\/code> \u65e2\u53ef\u4ee5\u4f5c\u4e3a S \u7684\u7b2c 1 \u5230 3 \u4e2a\u5b57\u7b26\u7684\u5b50\u4e32\uff0c\u4e5f\u53ef\u4ee5\u4f5c\u4e3a\u7b2c 8 \u5230 10 \u4e2a\u5b57\u7b26\u7684\u5b50\u4e32\uff0c\u4f46\u7531\u4e8e\u53d6\u51fa\u4f4d\u7f6e\u4e0d\u540c\uff0c\u5b83\u4eec\u88ab\u89c6\u4e3a\u4e0d\u540c\u7684\u5b50\u4e32\u8fdb\u884c\u8ba1\u6570\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u6837\u4f8b\u89e3\u91ca 2<\/h3>\n\n\n\n<p class=\"wp-block-paragraph\">S \u7684\u6240\u6709\u975e\u7a7a\u5b50\u4e32\u90fd\u5305\u542b T \u4f5c\u4e3a\u5b50\u5e8f\u5217\u3002\u56e0\u6b64\u6ca1\u6709\u6ee1\u8db3\u6761\u4ef6\u7684\u5b50\u4e32\uff0c\u8f93\u51fa 0\u3002<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">\u6570\u636e\u8303\u56f4<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>S \u7531\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210<\/li>\n\n\n\n<li>\u8bb0 |S| \u4e3a S \u7684\u957f\u5ea6\uff0c\u6ee1\u8db3$ 1 \\le |S| \\le 2 \\times 10^5$<\/li>\n\n\n\n<li>T \u7531\u5c0f\u5199\u82f1\u6587\u5b57\u6bcd\u7ec4\u6210<\/li>\n\n\n\n<li>\u8bb0 |T| \u4e3a T \u7684\u957f\u5ea6\uff0c\u6ee1\u8db3$ 1 \\le |T| \\le 50$<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">\u4ee3\u7801<\/h2>\n\n\n\n<pre class=\"wp-block-code\"><code>\/\/&nbsp;Sunshine,&nbsp;sunshine,&nbsp;ladybugs&nbsp;awake!  \n\/\/&nbsp;Clap&nbsp;your&nbsp;hooves&nbsp;and&nbsp;do&nbsp;a&nbsp;little&nbsp;shake!  \n#include&nbsp;&lt;bits\/stdc++.h&gt;  \n#define&nbsp;int&nbsp;long&nbsp;long  \n#define&nbsp;endl&nbsp;'\\n'  \nusing&nbsp;namespace&nbsp;std;  \n  \nusing&nbsp;PII=pair&lt;int,int&gt;&nbsp;;  \nusing&nbsp;PIC=pair&lt;int,char&gt;&nbsp;;  \ninline&nbsp;static&nbsp;constexpr&nbsp;int&nbsp;MAXN=200010;  \ninline&nbsp;static&nbsp;constexpr&nbsp;int&nbsp;mod=676767677;  \n  \nvoid&nbsp;solve()&nbsp;{  \n&nbsp;&nbsp;&nbsp;&nbsp;string&nbsp;s,t;  \n&nbsp;&nbsp;&nbsp;&nbsp;cin&gt;&gt;s&gt;&gt;t;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;n=s.size(),m=t.size();  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;vector&lt;array&lt;int,26&gt;&gt;&nbsp;nxt(n+1);  \n&nbsp;&nbsp;&nbsp;&nbsp;nxt&#91;n].fill(n);  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;i=n-1;i&gt;=0;i--){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nxt&#91;i]=nxt&#91;i+1];  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;nxt&#91;i]&#91;s&#91;i]-'a']=i;  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;ans=0;  \n&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;L=0;L&lt;n;L++){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;curr=L;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;bool&nbsp;flag=true;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;for(int&nbsp;j=0;j&lt;m;j++){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(curr==n){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag=false;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curr=nxt&#91;curr]&#91;t&#91;j]-'a'];  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(curr==n){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;flag=false;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;curr++;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if(flag){  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans+=(curr-1)-L;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}else{  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ans+=n-L;  \n&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;}  \n&nbsp;&nbsp;&nbsp;&nbsp;cout&lt;&lt;ans&lt;&lt;endl;  \n}  \n  \nsigned&nbsp;main()&nbsp;{&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ios_base::sync_with_stdio(false);  \n&nbsp;&nbsp;&nbsp;&nbsp;cin.tie(NULL);  \n&nbsp;&nbsp;&nbsp;&nbsp;\/\/int&nbsp;t;cin&nbsp;&gt;&gt;&nbsp;t;while&nbsp;(t--)&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;solve();  \n&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;0;  \n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>AT_abc452_d [ABC452D] No-Subsequence Substring \u9898\u76ee\u63cf\u8ff0 \u7ed9\u5b9a\u7531 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":132,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,11,10],"tags":[],"class_list":["post-161","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-atc","category-11","category-10"],"_links":{"self":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/161","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/comments?post=161"}],"version-history":[{"count":2,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/161\/revisions"}],"predecessor-version":[{"id":200,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/posts\/161\/revisions\/200"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media\/132"}],"wp:attachment":[{"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/media?parent=161"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/categories?post=161"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/huxiaole.cloud\/index.php\/wp-json\/wp\/v2\/tags?post=161"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}