1 条题解
-
0
题目分析
令 表示从字符串的 位置和 位置开始,能够满足 相似的最长长度。
可以用尺取法在 的复杂度中求出来。
具体做法是:
- 枚举两个位置的间隔距离 ;
- 枚举 和 , 从 开始, 从 开始;
- 若 ,那么 就是 减去位置 和位置 的距离,再继续往后匹配;
- 对于每个 ,匹配的最后位置单调不减。
设 表示在 后面分割,能找出的 相似字符串对数。
枚举位置 和位置 ,考虑以 和 为起始位置的字符串的贡献。
设 。
也就是说 ,……,。
所以如果分割位置在 ,以 和 为起始位置的字符串会有 的贡献,即 与 。
- 如果分割位置在 ,有 的贡献,即 与 , 与 ;
- 如果分割位置在 ,有 的贡献。
- ……
- 直到分割位置在 ,有 的贡献。
当分割位置在 后面且在 前面,都是有 的贡献。
当分割位置在 后面,因为要求分割位置左右各选一个子串,所以无贡献。
另外, 不能超过分割位置,所以 与 取小。
我们看以 和 为起始位置的字符串对不同的分割位置产生的贡献:
$0,0,0,1,2,3,\ldots,f[i][j]-2,f[i][j]-1,f[i][j],f[i][j],f[i][j],0,0,0$。
最前面的 是从分割位置 开始的,到分割位置 贡献依次加 ,然后从分割位置 开始贡献都是 不变,再从分割位置 后贡献都是 。
对这个贡献做一次差分得到 …… 。
再做一次差分得到二阶差分 …… 。
对于每一对 和 ,在答案的二阶差分里只修改 个位置。
位置 , 位置 , 位置 , 位置 。
最后求两次前缀和还原答案序列。
小细节:在求 时,匹配位置可能超过 。
在字符串的最后加一个特殊字符,然后限定匹配到 ,因为程序写法是到不合法位置停止。
#include<bits/stdc++.h> using namespace std; #define N 3002 char s[N]; int f[N][N]; long long ans[N]; int main() { int n,m,dis,len,k; scanf("%d%d",&n,&m); scanf("%s",s+1); for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) f[i][j]=0; for(int i=1;i<n;++i) ans[i]=0; s[n+1]='#'; for(int d=1;d<n;++d) { dis=0; len=0; for(int i=1,j=i+d;j<=n;++i,++j) { while(dis<=m && j+len<=n+1) { dis+=s[i+len]!=s[j+len]; ++len; } f[i][j]=len-1; dis-=s[i]!=s[j]; len--; } } for(int i=1;i<=n;++i) for(int j=i+1;j<=n;++j) { ans[i]++; k=min(j-i,f[i][j]); ans[i+k]--; ans[j]-=k; ans[j+1]+=k; } for(int i=2;i<n;++i) ans[i]+=ans[i-1]; for(int i=2;i<n;++i) ans[i]+=ans[i-1]; for(int i=1;i<n;++i) printf("%lld\n",ans[i]); return 0; }
- 1
信息
- ID
- 148
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 2
- 已通过
- 1
- 上传者