本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-03-24 11:19:06

题意

给出整数 $N$ 和两个字符串 $S$ 和 $T$，将字符串 $S$ 整体复制 $N$ 次拼接起来得到母串，要求把 $T$ 中每个字符分别复制 $k$ 次再拼接起来得到的串为母串的子序列，求 $k$ 的最大值。

思路

显然，若 $k$ 合法，则 $k-1$ 只需在 $k$ 的取法上把原串中每个字符少取一个即可，因此具有单调性，可以二分答案。

现在需要写出check函数，考虑反过来做，对于一个 $k$ 值求出需要复制 $S$ 串的次数，再与 $N$ 比较来check。

这样问题就成了求把 $T$ 中每个字母按顺序分别取 $k$ 个所需的 $S$ 数量。为了求出这个数量，需要维护 $S$ 串中各字母出现的后缀次数以及各字母出现的位置，具体看下边的代码实现吧。

这里要注意二分的上界，设 $S$ 长度为 $ls$，$T$ 长度为 $lt$，若 $N$ 个 $S$ 串被尽可能利用，最多能使 $k$ 达到 $\lfloor \frac{n\times ls}{lt}\rfloor$，以此为二分上界能在不爆longlong的前提下通过。

代码

#include<iostream>
#include<vector>
#include<cstring>
#define int long long
using namespace std;
const int N=1e5+10;
const int K=26+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,ls,lt;
char s[N],t[N];
int a[N][K];\/\/a_i 记录s串中第i位到末尾 各个字母出现次数
vector <int> pos[K];\/\/pos_i 记录s串中第i个字母出现的位置 
bool check(int x)
{
	if(x==0) return true;
	int cnt=0,lpos=ls;\/\/cnt表示构成g(T,x)需要的s串个数，lpos表示上一个s串用到了第(lpos-1)位 
	for(int i=0;i<lt;i++)\/\/构成每个字母 
	{
		int tc=t[i]-'a',ts=x;\/\/需要的字符及数量 
		if(ts<=a[lpos][tc]) \/\/如果上一个s串中剩余的tc足够
			lpos=pos[tc][a[0][tc]-a[lpos][tc]+ts-1]+1;\/\/只需修改使用到的位置 
		else
		{
			ts-=a[lpos][tc];\/\/先把上个串用完 
			cnt+=ts\/a[0][tc];\/\/再用完整的若干个串 
			ts%=a[0][tc];\/\/还需要多少个该字母 
			if(ts) 
			{
				cnt++;
				lpos=pos[tc][ts-1]+1;
			}\/\/如果还需要，就多用一个串并记录位置 
			else lpos=pos[tc][a[0][tc]-1]+1;\/\/否则记录s串中该字母最后一次出现的位置即可 
		} 
	}
	return cnt<=n;\/\/判断是否合法 
}
signed main()
{
	n=read();
	cin>>s>>t;
	ls=strlen(s),lt=strlen(t);
	for(int i=ls-1;i>=0;i--)
	{
		for(int j=0;j<26;j++) a[i][j]=a[i+1][j];
		a[i][s[i]-'a']++;
	}\/\/倒序处理后缀a数组 
	for(int i=0;i<lt;i++) if(!a[0][t[i]-'a'])
	{
		cout<<0;
		return 0;
	}\/\/这里特判：若t串中有s串没有的字符，则直接输出0
	\/\/如果不判的话，在check函数里会除以0寄掉 
	for(int i=0;i<ls;i++) pos[s[i]-'a'].push_back(i);\/\/正序记录各字母出现位置 
	int l=0,r=n*ls\/lt,ans;\/\/这里二分上界要注意 
	while(l<=r)
	{
		int mid=(l+r)\/2;
		if(check(mid)) ans=mid,l=mid+1;
		else r=mid-1;
	}\/\/二分答案 
	cout<<ans;
	return 0;
}