山西网站建设价格,东莞报告1例,个人网站能不能做论坛,discuz 轉wordpress文章目录题目描述解析代码题目描述 解析
显然应该要尝试套kmp的板子 关键是如何套 也就是那个判断匹配的条件是什么的问题
本题的关键是当kmp匹配时#xff0c;匹配位之前的所有位大小关系的顺序都是匹配的#xff0c;所以我们只需要看当前位即可 考虑对b预处理出3个数组匹配位之前的所有位大小关系的顺序都是匹配的所以我们只需要看当前位即可 考虑对b预处理出3个数组 id1[i][1,i-1]中与i相等的最靠右的数与i的距离 id2[i][1,i-1]中比i小的最大的数中最靠右的与i的距离 id3[i][1,i-1]中比i大的最小的数中最靠右的与i的距离 其实不是最靠右也可以啦只是最靠右容易求 对于”最靠右“的条件我们可以先顺序对每个值做一个栈记录这个值出现过的位置然后逆序求每次再把自己的值对应的栈弹出一个首元素 “比i小的最大”这样的条件我们可以以值域为关键字建一个双向链表把一开始就没有的和弹出没有了的值都删除掉直接找 l 或 r 指针即可
然后就是这个判断。 假设当前A匹配到了[i-j1,i],B数组匹配到了[1,j] 利用这三个数组有三个对A失配的条件 若id1[j]存在且a[i1-id1[j1]]!a[i1]则失配 若id2[j]存在且a[i1-id2[j1]]a[i1]则失配 若id3[j]存在且a[i1-id3[j1]]a[i1]则失配 这个画画图还是不难理解的这是一个充要条件 问题得到解决
代码
#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 s;
int a[N],b[N];
int id1[N],id2[N],id3[N];
vectorintzhan[N];
int top[N];
int l[N],r[N];
void build(){for(int i1;is;i){l[i]i-1;r[i]i1;}l[s1]s;r[0]1;
}
void del(int x){l[r[x]]l[x];r[l[x]]r[x];}
int ask(int x,int y){return xy?x:0;}int p[N];
int ans,st[N];
void solve(){p[1]0;for(int i1,j0;im;i){while(j((ask(id1[j1],j1)b[i1-id1[j1]]!b[i1])||(ask(id2[j1],j1)b[i1-id2[j1]]b[i1])||(ask(id3[j1],j1)b[i1-id3[j1]]b[i1]))) jp[j];if(!((ask(id1[j1],j1)b[i1-id1[j1]]!b[i1])||(ask(id2[j1],j1)b[i1-id2[j1]]b[i1])||(ask(id3[j1],j1)b[i1-id3[j1]]b[i1]))) j;p[i1]j;//printf(i%d p%d\n,i1,j);}
}
void kmp(){for(int i0,j0;in;i){while(j((ask(id1[j1],j1)a[i1-id1[j1]]!a[i1])||(ask(id2[j1],j1)a[i1-id2[j1]]a[i1])||(ask(id3[j1],j1)a[i1-id3[j1]]a[i1]))){//printf( i1%d j%d %d: %d!%d? %d: %d%d? %d: %d%d? \n,i1,j,ask(id1[j1],j1),a[i1-id1[j1]],a[i1],ask(id1[j1],j1),a[i1-id2[j1]],a[i1],ask(id2[j1],j1),a[i1-id1[j1]],a[i1]);jp[j];} if(!((ask(id1[j1],j1)a[i1-id1[j1]]!a[i1])||(ask(id2[j1],j1)a[i1-id2[j1]]a[i1])||(ask(id3[j1],j1)a[i1-id3[j1]]a[i1]))) j;//printf(i%d p%d\n,i1,j);if(jm){st[ans]i1-m1;jp[j];}}
}
int main(){scanf(%d%d%d,n,m,s);for(int i1;in;i) scanf(%d,a[i]);for(int i1;im;i) scanf(%d,b[i]);for(int i1;is;i){zhan[i].push_back(0);//zhan[i][0]0;}for(int i1;im;i){zhan[b[i]].push_back(i);//zhan[b[i]][top[b[i]]]i;top[b[i]];}build();for(int i1;is;i){if(!top[i]) del(i);}for(int im;i1;i--){int xl[b[i]],yr[b[i]];if(x) id2[i]i-zhan[x][top[x]];if(ys) id3[i]i-zhan[y][top[y]];if(!--top[b[i]]) del(b[i]);else id1[i]i-zhan[b[i]][top[b[i]]];//printf(i%d id1%d id2%d id3%d\n,i,id1[i],id2[i],id3[i]);}solve();kmp();printf(%d\n,ans);for(int i1;ians;i){printf(%d\n,st[i]);}return 0;
}
/*
9 6 10
5 6 2 10 10 7 3 2 9
1 4 4 3 2 16 4 10
3 5 2 7 1 9
3 8 2 10
*/
