唯一分割的结构:由于 x 不含 x 与 y,整串必然呈现反复的模式:一段由非 x,y 字符构成的连续块 x,随后紧跟着 "xy";如此反复直到串末。
线性扫描:从左到右扫描:
x,y 字符组成的连续块作为当前的 x;"xy" 后结束该段,将该 x 放入集合;"xy" 继续下一段。正确性:每一段的 x 恰为紧邻其后的 "xy" 之前的最长非 x,y 连续块;由于 x 不能含 x,y 且分割唯一,上述扫描会精确得到每个 x,且不会遗漏或重复切分。
在某种通信协议中,一条消息由若干个数据帧首尾拼接而成。每个数据帧的格式形如:一个非空的名称后紧跟固定的两字符尾标 xy。名称由小写字母组成,且名称中不能包含字符 x 和 y。
现给定一个合法的完整消息字符串,保证其能够唯一地分割成若干个满足上述格式的数据帧。请你统计消息中一共出现了多少种不同的名称。
字符串的长度满足 3≤∣s∣≤106,且仅由小写字母组成。
一行输入一个仅包含小写字母的字符串 s,表示完整的消息。字符串长度满足 3≤∣s∣≤106,且保证可以被唯一地分割为一个或多个“名称 + xy”的段。
开通会员即可查看完整视频题解: 1.题目讲解 2.思路分析 3.逐行代码手写
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册