← 返回题目

题库练习项链

← 上一题下一题 →

A2776 | $项链$

来源USACO / 2013

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

母牛贝茜安排了一串N块石头，每块石头都包含一个字母表，她想把它们做成一条时尚的项链。 为了保护自己的财物，贝茜不想与目前住在谷仓一侧的另一头母牛分享她的项链。另一头牛的名字是一串 M 字符，Bessie 希望确保这根长度为 M 的绳子不会在代表她的项链的绳子的任何位置作为连续的子串出现（否则，另一头牛可能会误以为项链是给她的）。贝茜决定去掉项链上的一些石头，这样另一头牛的名字就不会以子绳的形式出现。请帮助贝茜确定她必须清除的最小岩石数量。

输入格式

* 第 1 行：第一行是一条长度为 N 的字符串，描述了 Bessie 最初的项链;每个字符都在“a”到“z”的范围内。 * 第 2 行：第二行是谷仓中另一头奶牛的长度 M 名称，也由“a”到“z”的字符组成。

输出格式

* 第 1 行：需要从 Bessie 的项链中移除的最小宝石数量，以便它不包含另一头牛的名字作为子字符串。

输入输出样例

输入 #1

ababaa 
aba

输出 #1

C++ 编辑器

输入

输出