当前位置:首页 > 离散化 > 哈希表 > 正文
洛谷P7469积木小赛[2021NOIOnline]
125+

题目大意:两个长度为n的字符串A和B,B中有多少种子串是A的子序列?

题目描述

Alice 和 Bob 最近热衷于玩一个游戏——积木小赛。

Alice 和 Bob 初始时各有 块积木从左至右排成一排,每块积木都被标上了一个英文小写字母。

Alice 可以从自己的积木中丢掉任意多块(也可以不丢);Bob 可以从自己的积木中丢掉最左边的一段连续的积木和最右边的一段连续的积木(也可以有一边不丢或者两边都不丢)。两人都不能丢掉自己所有的积木。然后 Alice 和 Bob 会分别将自己剩下的积木按原来的顺序重新排成一排。

Alice 和 Bob 都忙着去玩游戏了,于是想请你帮他们算一下,有多少种不同的情况下他们最后剩下的两排积木是相同的。

两排积木相同,当且仅当这两排积木块数相同且每一个位置上的字母都对应相同。

两种情况不同,当且仅当 Alice(或者 Bob)剩下的积木在两种情况中不同。

输入格式

第一行一个正整数 ,表示积木的块数。

第二行一个长度为 的小写字母串 ,表示 Alice 初始的那一排积木,其中第 个字母 表示第 块积木上的字母。

第三行一个长度为 的小写字母串 ,表示 Bob 初始的那一排积木,其中第 个字母 表示第 块积木上的字母。

输出格式

一行一个非负整数表示答案。

输入输出样例

输入 #1
5
bcabc
bbcca
输出 #1
9
输入 #2
20
egebejbhcfabgegjgiig
edfbhhighajibcgfecef
输出 #2
34

说明/提示

对于所有测试点: 中只包含英文小写字母。

测试点 满足: 中只包含同一种字母。

测试点 满足:

测试点 满足:

测试点 满足:

解题思路

暴力枚举B的字串,判重后判断是否A的子序列,时间复杂度$O(n^3)$。

再观察一下,发现字串有重叠的,开头是i的,有i、i..i+1、i..n等等,可以依次尝试查找匹配,找到就累计答案,只是需要判重而已。

程序实现

双哈希判断字符串是否重复,错误率更低;双哈希判重,冲突率小,查找效率高。

About

坚决不Copy代码!

本文标签:,,,,,,,,,

洛谷P7469积木小赛[2021NOIOnline]:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter