【bzoj4641】基因改造 特殊匹配条件的KMP
2024-09-03 20:30:06
题目描述
如果两个长度相等的字符串,如果存在一种字符的一一映射,使得第一个字符串的所有字符经过映射后与第二个字符串相同,那么就称它们“匹配”。现在给出两个串,求第一个字符串所有长度等于第二个字符串的长度的子串中与第二个字符串“匹配”的所有子串的位置。
输入
输入文件的第一行包含两个正整数case和C,分别表示数据组数和人类智慧脱氧核苷酸的种数。
接下来3*case行,每三行表示一组数据:
第一行一个正整数N和M,表示人类智慧DNA片段S和TB智慧DNA片段T的长度。
第二行N个正整数,表示人类智慧DNA片段S。
第三行M个正整数,表示TB智慧DNA片段T。
对于所有数据数据,case=3, n,m,C<=1000000
输出
对于每组数据:
第一行一个正整数tot,表示"萌萌哒人类基因片段"的个数。
接下来一行tot个用空格隔开的正整数pos,表示"萌萌哒人类基因片段"开头所在的位置。要求从小到大输出每个pos。
样例输入
3 3
6 3
1 2 1 2 3 2
3 1 3
6 3
1 2 1 2 1 2
3 1 3
6 3
1 1 2 1 2 1
3 1 3
样例输出
3
1 2 4
4
1 2 3 4
3
2 3 4
题解
特殊匹配条件的KMP
本题和 【bzoj2384】[Ceoi2011]Match 类似。
考虑什么样的两个串是“匹配”的:每个位置数的上一次出现位置与其距离相同。
那么可以把每个位置的权值当作该数上一次出现的位置与其的距离,然后跑KMP即可。
这里需要注意的一点是,在求next数组和匹配时,如果一个位置的上一次出现位置与其距离大于当前串长(这种情况在求next计算后半部分,以及匹配时的母串中出现),那么应当视为该数没有出现过,需要特殊处理。
时间复杂度 $O(n)$
#include <cstdio>
#include <cctype>
#include <cstring>
#define N 1000010
int pa[N] , pb[N] , pos[N] , next[N] , ans[N];
inline char nc()
{
static char buf[100000] , *p1 , *p2;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf , 1 , 100000 , stdin) , p1 == p2) ? EOF : *p1 ++ ;
}
inline int read()
{
int ret = 0; char ch = nc();
while(!isdigit(ch)) ch = nc();
while(isdigit(ch)) ret = ((ret + (ret << 2)) << 1) + (ch ^ '0') , ch = nc();
return ret;
}
int main()
{
int T = read();
read();
while(T -- )
{
int n = read() , m = read() , i , j , x , tot = 0;
memset(pos , -1 , sizeof(pos));
for(i = 0 ; i < n ; i ++ ) x = read() , pa[i] = (~pos[x] ? i - pos[x] : -1) , pos[x] = i;
memset(pos , -1 , sizeof(pos));
for(i = 0 ; i < m ; i ++ ) x = read() , pb[i] = (~pos[x] ? i - pos[x] : -1) , pos[x] = i;
next[0] = -1;
for(i = 1 , j = -1 ; i <= m ; i ++ )
{
while(~j && pb[i - 1] != pb[j] && !(pb[i - 1] > j && pb[j] == -1)) j = next[j];
next[i] = ++j;
}
for(i = j = 0 ; i < n ; i ++ )
{
while(~j && pa[i] != pb[j] && !(pa[i] > j && pb[j] == -1)) j = next[j];
if(++j == m) ans[++tot] = i - m + 2 , j = next[j];
}
printf("%d\n" , tot);
for(i = 1 ; i <= tot ; i ++ ) printf("%d " , ans[i]);
printf("\n");
}
return 0;
}
最新文章
- activitygroup下的activity不回调onactivityresult的解决方法
- div布局
- 笔记13:File 类的一些操作
- ASP.NET MVC 程序 报错“CS0012: 类型“System.Data.Objects.DataClasses.EntityObject”在未被引用的程序集中定义”的解决办法
- linux截图工具scrot
- SaaS系列介绍之十四: SaaS软件开发分析
- python+xlsxwriter+PIL自动压图贴图到Excel小工具
- AJAX原理解析与兼容方法封装
- 7、Dockerfile详解
- 【持续更新】JAVA面向对象多线程编程的一些tips
- u盘系统安装步骤
- 从 ELK 到 EFK 的演进
- HTML5之pushstate、popstate操作history,无刷新改变当前url
- vue 操作数组,原数组怎么不让它改变
- DataRow对象的RowState和DataRowVersion属性特点
- Eutils用法总结
- **Python的函数参数传递 和 global
- 【总结整理】word使用技巧
- JAVA反映练手
- Elasticsearch5.3 学习(一):安装、Yii2.0 下载es扩展