#P3075. [Usaco2013]Necklace

    ID: 2208 传统题 1000ms 512MiB 尝试: 84 已通过: 49 难度: 6 上传者: 标签>CF2000提高KMP 自动机 DP预计算转移禁止模式状态过滤滚动数组Gold

[Usaco2013]Necklace

题目描述

贝西收集了 NN 颗石头,每颗石头上都有一个字母,贝西想把这些石头做成项链。

贝西的身边有另一只奶牛,这只奶牛的名字是一个长度为 MM 的字符串,贝西不希望这只牛的名字出现在她的项链上(项链的子串),她想知道,最少删掉几颗石头就可以避免这种情况发生。

输入格式

第一行:一个长度为 NN 的字符串,描述贝西的初始项链,每个字符的取值范围为 "a" 到 "z"。

第二行:一个长度为 MM 的字符串,表示另一只牛的名字,每个字符的取值范围为 "a" 到 "z"。

输出格式

输出一行,表示需要从贝西的项链中移除的最少石头数量,以确保项链中不包含另一牛的名字作为子串。

输入样例

ababaa 
aba

输出样例

1

数据范围

至少 20%20\% 的测试点,N≤20N \le 20。 至少 60%60\% 的测试点,N≤1000N \le 1000,M≤100M \le 100。 对于所有测试点,N≤10000N \le 10000,M≤1000M \le 1000。 对于所有测试点,M≤NM \le N。

upd 2022.7.29\text{upd 2022.7.29}:新增加一组 Hack 数据。