3358. 放养但没有完全放养
摘要
Title: 3358. 放养但没有完全放养
Tag: 双指针
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
3358. 放养但没有完全放养
-
题意
一个鲜为人知的事实是，奶牛拥有自己的文字：「牛文」。
牛文由 26 个字母 a 到 z 组成，但是当奶牛说牛文时，可能与我们所熟悉的 abcdefghijklmnopqrstuvwxyz 不同，她会按某种特定的顺序排列字母。
为了打发时间，奶牛 Bessie 在反复哼唱牛文字母歌，而 Farmer John 好奇她唱了多少遍。
给定一个小写字母组成的字符串，为 Farmer John 听到 Bessie 唱的字母，计算 Bessie 至少唱了几遍完整的牛文字母歌，使得 Farmer John 能够听到给定的字符串。
Farmer John 并不始终注意 Bessie 所唱的内容，所以他可能会漏听 Bessie 唱过的一些字母。
给定的字符串仅包含他记得他所听到的字母。 -
思路
注意到模板串最多1000，也就是字母表最长 26 * 1000，所以可以直接拉长字母表，双指针匹配即可，最后上取整
板子题：2816. 判断子序列
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19'''
Author: NEFU AB-IN
Date: 2022-03-15 10:44:21
FilePath: \ACM\Acwing\3358.py
LastEditTime: 2022-03-15 10:44:21
'''
s = input()
s = s * 1001
start = s[0]
p = input()
j = 0
for i in range(len(p)):
while j < len(s) and s[j] != p[i]:
j += 1
j += 1
print((j + 26) // 26)