A22487.项链
提高+/省选-
USACO
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
母牛贝茜安排了一串N块石头,每块石头都包含一个字母表,她想把它们做成一条时尚的项链。
为了保护自己的财物,贝茜不想与目前住在谷仓一侧的另一头母牛分享她的项链。另一头牛的名字是一串 M 字符,Bessie 希望确保这根长度为 M 的绳子不会在代表她的项链的绳子的任何位置作为连续的子串出现(否则,另一头牛可能会误以为项链是给她的)。贝茜决定去掉项链上的一些石头,这样另一头牛的名字就不会以子绳的形式出现。请帮助贝茜确定她必须清除的最小岩石数量。
输入格式
-
第 1 行:第一行是一条长度为 N 的字符串,描述了 Bessie 最初的项链;每个字符都在“a”到“z”的范围内。
-
第 2 行:第二行是谷仓中另一头奶牛的长度 M 名称,也由“a”到“z”的字符组成。
输出格式
- 第 1 行:需要从 Bessie 的项链中移除的最小宝石数量,以便它不包含另一头牛的名字作为子字符串。
输入输出样例
输入#1
ababaa aba
输出#1
1
说明/提示
For at least 20% of test cases, N <= 20.
For at least 60% of test cases, N <= 1000, M <= 100.
For all test cases, N <= 10000, M <= 1000.
For all test cases, M <= N.