网站的最终用户,新网官方网站登陆,常州网站搭建公司,公司设计一个网站需要多久文章目录题目描述解析代码题目描述 解析
看了题解。。。 这题的关键在于可以变换匹配的一个充要条件#xff1a; 每个字符与前一个相同字符的距离相同 这个搞出来之后就可以以它为关键字进行KMP了 注意#xff01; 当与前一个字符的距离超过匹配长度时#xff0c;是没有意义…
文章目录题目描述解析代码题目描述 解析
看了题解。。。 这题的关键在于可以变换匹配的一个充要条件 每个字符与前一个相同字符的距离相同 这个搞出来之后就可以以它为关键字进行KMP了 注意 当与前一个字符的距离超过匹配长度时是没有意义的应该当做首次出现处理
代码
#includebits/stdc.h
using namespace std;
#define ll long long
typedef unsigned long long ull;
const int N 1e6100;
const int M1e75;
const int mod1e97;
int n,m;
int t,c;
int a[N],b[N],st[N],ans;
int last[N],prea[N],preb[N];
int p[N];
int ask(int x,int y){return xy?x:0;}
void solve(){p[1]0;for(int i1,j0;im;i){while(jask(preb[i1],j1)!ask(preb[j1],j1)) jp[j];if(ask(preb[i1],j1)ask(preb[j1],j1)) j;p[i1]j;//printf(i%d p%d\n,i1,j);}
}
void find(){ans0;for(int i0,j0;in;i){while(jask(prea[i1],j1)!ask(preb[j1],j1)) jp[j];if(ask(prea[i1],j1)ask(preb[j1],j1)) j;//printf(i%d j%d\n,i1,j);if(jm){st[ans]i1-m1;jp[j];}}
}
int main(){scanf(%d%d,t,c);while(t--){scanf(%d%d,n,m);memset(last,0,sizeof(last));for(int i1;in;i) scanf(%d,a[i]);for(int i1;im;i) scanf(%d,b[i]);for(int i1;in;i){prea[i]ask(i-last[a[i]],m);last[a[i]]i;//printf(i%d pre%d\n,i,prea[i]);}memset(last,0,sizeof(last));for(int i1;im;i){preb[i]ask(i-last[b[i]],m);last[b[i]]i;}solve();find();printf(%d\n,ans);for(int i1;ians;i) printf(%d ,st[i]);printf(\n);}return 0;
}
