Hard KMP Problem
题号:NC262358
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 512 M,其他语言1024 M
64bit IO Format: %lld

题目描述

给定两个串 ST,你可以对这两个串分别进行重排,定义匹配度为最大的非负整数 x 使得能从 S 中选出 x 个不相交子串满足这几个子串都等于 T。请问重排后能获得的最大匹配度为多少。

输入描述:

本题多组数据。

第一行一个数 t(1\leq t\leq 5),表示数据组数。

对于每组数据,一行为两个字符串 S,T(1\leq |S|,|T|\leq 10^5),保证字符集为小写字母集。

输出描述:

T 个数,表示答案。
示例1

输入

复制
2
abcadc
ac
bbbbbbb
bd

输出

复制
2
0