P11582 [CCC 2020] Searching for Strings题目背景本题译自 Canadian Computing Competition 2020 Senior T3 Searching for Strings。题目描述计算字符串n nn的不同排列中作为h hh的子字符串的数量。输入格式第一行一个字符串n ( 1 ≤ ∣ n ∣ ≤ 2 × 10 5 ) n(1 \le |n| \le 2\times10^5)n(1≤∣n∣≤2×105)。第二行一个字符串h ( 1 ≤ ∣ h ∣ ≤ 2 × 10 5 ) h(1 \le |h| \le 2\times10^5)h(1≤∣h∣≤2×105)。保证这两个串只含小写字母。输出格式输出由一个整数构成即题目所求。输入输出样例 #1输入 #1aab abacabaa输出 #12说明/提示本题采用捆绑测试。【样例解析】仅有排列aba和baa作为子字符串出现在了h hh中。【数据范围】设n nn长度为x xxh hh长度为y yy。Subtask特殊性质分值1x ≤ 8 , y ≤ 200 x\le 8,y\le 200x≤8,y≤200202x ≤ 200 , y ≤ 200 x\le 200,y\le 200x≤200,y≤200143x ≤ 2000 , y ≤ 2000 x\le 2000,y\le 2000x≤2000,y≤2000144无52注原题满分为 15 分其中 Sub1 有3 33分Sub2 和 Sub3 有2 22分而 Sub4 有8 88分。本题分数为取近似后得到的结果。C实现#includeiostream#includesetusingnamespacestd;string a,b;setunsignedlonglongst;unsignedlonglongh[200001],pw[200001];voidHash(conststrings){constintlens.size();for(inti0;ilen;i)h[i1]h[i]*131s[i];}unsignedlonglongsub_Hash(intl,intr){// 求区间 [l,r] 的哈希值returnh[r]-h[l-1]*pw[r-l1];}voidinit(){for(registerinti*pw1;i200000;i)pw[i]pw[i-1]*131;}intanum[128],bnum[128];intmain(){cin.tie(nullptr)-sync_with_stdio(false),cout.tie(nullptr);cinab;init();Hash(b);constintlena.size();for(inti0;ilen;i)anum[a[i]];// anum[c] 表示字符串 a 中字符 c 出现次数for(intj,i0;ib.size();i){bnum[b[i]];// bnum[c] 表示当前枚举的 b 的子串中字符 c 出现次数if(ilen)bnum[b[i-len]]--;if(ilen-1){for(j0;j128;j)if(anum[j]!bnum[j])break;// 此时枚举的子串不是字符串 a 的排列if(j128)st.insert(sub_Hash(i-len2,i1));}}coutst.size();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
打卡信奥刷题（3592）用C++实现信奥题 P11582 [CCC 2020] Searching for Strings
P11582 [CCC 2020] Searching for Strings题目背景本题译自 Canadian Computing Competition 2020 Senior T3 Searching for Strings。题目描述计算字符串n nn的不同排列中作为h hh的子字符串的数量。输入格式第一行一个字符串n ( 1 ≤ ∣ n ∣ ≤ 2 × 10 5 ) n(1 \le |n| \le 2\times10^5)n(1≤∣n∣≤2×105)。第二行一个字符串h ( 1 ≤ ∣ h ∣ ≤ 2 × 10 5 ) h(1 \le |h| \le 2\times10^5)h(1≤∣h∣≤2×105)。保证这两个串只含小写字母。输出格式输出由一个整数构成即题目所求。输入输出样例 #1输入 #1aab abacabaa输出 #12说明/提示本题采用捆绑测试。【样例解析】仅有排列aba和baa作为子字符串出现在了h hh中。【数据范围】设n nn长度为x xxh hh长度为y yy。Subtask特殊性质分值1x ≤ 8 , y ≤ 200 x\le 8,y\le 200x≤8,y≤200202x ≤ 200 , y ≤ 200 x\le 200,y\le 200x≤200,y≤200143x ≤ 2000 , y ≤ 2000 x\le 2000,y\le 2000x≤2000,y≤2000144无52注原题满分为 15 分其中 Sub1 有3 33分Sub2 和 Sub3 有2 22分而 Sub4 有8 88分。本题分数为取近似后得到的结果。C实现#includeiostream#includesetusingnamespacestd;string a,b;setunsignedlonglongst;unsignedlonglongh[200001],pw[200001];voidHash(conststrings){constintlens.size();for(inti0;ilen;i)h[i1]h[i]*131s[i];}unsignedlonglongsub_Hash(intl,intr){// 求区间 [l,r] 的哈希值returnh[r]-h[l-1]*pw[r-l1];}voidinit(){for(registerinti*pw1;i200000;i)pw[i]pw[i-1]*131;}intanum[128],bnum[128];intmain(){cin.tie(nullptr)-sync_with_stdio(false),cout.tie(nullptr);cinab;init();Hash(b);constintlena.size();for(inti0;ilen;i)anum[a[i]];// anum[c] 表示字符串 a 中字符 c 出现次数for(intj,i0;ib.size();i){bnum[b[i]];// bnum[c] 表示当前枚举的 b 的子串中字符 c 出现次数if(ilen)bnum[b[i-len]]--;if(ilen-1){for(j0;j128;j)if(anum[j]!bnum[j])break;// 此时枚举的子串不是字符串 a 的排列if(j128)st.insert(sub_Hash(i-len2,i1));}}coutst.size();return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容
