深圳网站建设服务,wordpress获取缩略图,广商网,营销型平台网站建设字符串匹配 【题目描述】 对于一个字符集大小为C的字符串pp#xff0c;可以将任意两个字符在p中的位置进行互换#xff0c;例如p12321#xff0c;交换1、21、2得到21312#xff0c;交换1、4得到42324#xff0c;交换可以进行任意次。若交换后p变成了字符串q#xff0c;则…字符串匹配 【题目描述】 对于一个字符集大小为C的字符串pp可以将任意两个字符在p中的位置进行互换例如p12321交换1、21、2得到21312交换1、4得到42324交换可以进行任意次。若交换后p变成了字符串q则成q与p是匹配的。 给定两个字符集大小为C的字符串s、t求出s中有多少个连续子串与t匹配。 【输入】 第一行两个整数T、C分别表示数据组数和字符集大小字符用1∼C的整数来表示。 对于每组数据第一行两个整数n、m分别表示s、t的长度。 第二行n个正整数表示s。 第三行m个正整数表示t。 【输出】 对于每组数据输出包括两行 第一行一个正整数k表示s中有k个连续子串与t匹配。 第二行从小到大输出k个数表示s中与t匹配的连续子串的首位下标下标从1开始。 【输入样例】 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 【数据规模及约定】 对于10%的数据满足n,m,C≤1000n,m,C≤1000 对于另外20%的数据满足n,m≤105C≤40n,m≤105C≤40 对于另外30%的数据满足n,m,C≤105n,m,C≤105 对于100%的数据满足1≤n,m,C≤106T31≤n,m,C≤106T3。 【分析】 这其实就是一道KMP的题 题目的难点在于如何交换字符 我们可以开一个数组l[1~c] l[x]表示上一个x出现的位置 a[i]表示字符s[i]离上一个相同字符出现的距离 b[i]表示字符t[i]离上一个相同字符出现的距离 然后就是KMP 难点是如何判断s[i](t[i])的上一个相同字符是否在模式串之外 这其实很简单 直接判断上一个x出现的距离是否大于j不就行了 于是开两个函数 inline int jdg(int x,int l){return xl?x:0;}//判断s[i](t[i])的上一个相同字符是否在匹配范围内//是就返回a[i](b[i])否就返回0
inline bool eq(int x,int y,int l){return jdg(x,l)jdg(y,l);}//判断是否匹配 经历千辛万苦 【AC代码】 #includecstdio
#includecstring
#includealgorithm
#define N (10000002)
#define C (10000002)
using namespace std;
int p[N];
int a[N],b[N];
int l[C];//这里很重要我把C开小了交了不知多少次都没有过
int ans[N];
templatetypename Tinline void read(T x){char tempgetchar();bool u0;for(x0;temp0||temp9;utemp-,tempgetchar());for(;temp0temp9;xx*10temp-0,tempgetchar());if(u)x-x;return ;
}//快读
inline int jdg(int x,int l){return xl?x:0;}//判断s[i](t[i])是否在匹配范围内//是就返回a[i](b[i])否就返回0
inline bool eq(int x,int y,int l){return jdg(x,l)jdg(y,l);}//判断是否匹配
void work(){register int i,j,x;register int n,m;read(n);read(m);memset(a,0,sizeof a);memset(b,0,sizeof b);//有多组数据一定要初始化memset(p,0,sizeof p);//否则就会成为某dengzhaoxing之二memset(l,0,sizeof l);for(i1;in;i){read(x);a[i]i-l[x];//将a[i]赋值为字符x与上一x之间的距离l[x]i;}memset(l,0,sizeof l);//输入s和t之前都要初始化lfor(i1;im;i){read(x);b[i]i-l[x];//将b[i]赋值为字符x与上一x之间的距离l[x]i;}for(i1,j0;im;i){while(j!eq(b[i1],b[j1],j1))jp[j];if(eq(b[i1],b[j1],j1))j;p[i1]j;}//KMP初始化p数组for(xij0;in;i){while(j!eq(a[i1],b[j1],j1))jp[j];if(eq(a[i1],b[j1],j1))j;if(jm){ans[x]i2-m;jp[j];}}//KMP匹配printf(%d\n,x);for(i1;ix;i)printf(%d ,ans[i]);//输出答案putchar(\n);return ;
}
int main(){register int t,c,i;read(t);read(c);for(i1;it;i)work();return 0;
}转载于:https://www.cnblogs.com/TbIblog/p/11247312.html
