Description
给出一个长度为\(n\)的字符串\(s\)和一个正整数\(k\)。定义两个长度相同且相差不超过\(k\)个字符的字符串是”k-matching“的，对于每个\(i\in[1,n-1]\)，求\(s_{1..i}\)的子串和\(s_{i+1..n}\)的子串有多少对是”k-matching“的。
Solution
反过来考虑每一对“k-matching”的子串对那些答案有贡献。首先搞出一个数组\(f(i,j)\)?????，记录\(s_{i...}\)?????和\(s_{j...}\)?????最远能匹配的长度，可以固定\(j-i\)??再用two-pointers解决。那么对于每对\(i,j\)?，它对答案的贡献如下：
| i-1 | i | i+1 | ... | i+f-2 | i+f-1 | i+f | ... | j-1 | j | j+1 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| \(ans\) | 0 | +1 | +2 | ... | +f-1 | +f | +f | +f | +f | 0 | 0 |
| 差分 | 0 | +1 | +1 | +1 | +1 | +1 | 0 | 0 | 0 | -f | 0 |
| 再差分 | 0 | +1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | -f | +f |
于是其对再差分数组的影响是\(O(1)\)的?，用\(f(i,j)\)更新完再差分数组再求两遍前缀和即可。
时间复杂度\(O(n^2)\)。
Code
//Another String
#include <algorithm>
#include <cstdio>
using std::min;
const int N=3e3+10;
int n,k; char s[N];
int f[N][N]; long long ans[N];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k); scanf("%s",s+1);
for(int d=1;d<=n;d++)
{
int len=0,cnt=0;
for(int i=1;i+d<=n;i++)
{
int j=i+d;
while(cnt<=k) cnt+=(s[i+len]!=s[j+len]),len++;
f[i][j]=min(len-1,min(d,n-j+1));
len--,cnt-=(s[i]!=s[j]);
}
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int len=f[i][j];
ans[i]++;
ans[i+len]--;
ans[j]-=len;
ans[j+1]+=len;
}
for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
for(int i=1;i<n;i++) printf("%lld\n",ans[i]);
for(int i=0;i<=n+2;i++) ans[i]=0;
}
return 0;
}
Description
给出一个长度为\(n\)的字符串\(s\)和一个正整数\(k\)。定义两个长度相同且相差不超过\(k\)个字符的字符串是”k-matching“的，对于每个\(i\in[1,n-1]\)，求\(s_{1..i}\)的子串和\(s_{i+1..n}\)的子串有多少对是”k-matching“的。
Solution
反过来考虑每一对“k-matching”的子串对那些答案有贡献。首先搞出一个数组\(f(i,j)\)?????，记录\(s_{i...}\)?????和\(s_{j...}\)?????最远能匹配的长度，可以固定\(j-i\)??再用two-pointers解决。那么对于每对\(i,j\)?，它对答案的贡献如下：
| \(i-1\) | \(i\) | \(i+1\) | ... | \(i+f-2\) | \(i+f-1\) | \(i+f\) | ... | \(j-1\) | \(j\) | \(j+1\) | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| \(ans\) | 0 | +1 | +2 | ... | +f-1 | +f | +f | +f | +f | 0 | 0 |
| 差分 | 0 | +1 | +1 | +1 | +1 | +1 | 0 | 0 | 0 | -f | 0 |
| 再差分 | 0 | +1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | -f | +f |
于是其对再差分数组的影响是\(O(1)\)的?，用\(f(i,j)\)更新完再差分数组再求两遍前缀和即可。
时间复杂度\(O(n^2)\)。
Code
//Another String
#include <algorithm>
#include <cstdio>
using std::min;
const int N=3e3+10;
int n,k; char s[N];
int f[N][N]; long long ans[N];
int main()
{
int T; scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k); scanf("%s",s+1);
for(int d=1;d<=n;d++)
{
int len=0,cnt=0;
for(int i=1;i+d<=n;i++)
{
int j=i+d;
while(cnt<=k) cnt+=(s[i+len]!=s[j+len]),len++;
f[i][j]=min(len-1,min(d,n-j+1));
len--,cnt-=(s[i]!=s[j]);
}
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
{
int len=f[i][j];
ans[i]++;
ans[i+len]--;
ans[j]-=len;
ans[j+1]+=len;
}
for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
for(int i=1;i<n;i++) printf("%lld\n",ans[i]);
for(int i=0;i<=n+2;i++) ans[i]=0;
}
return 0;
}