首页 > 代码库 > 【uva10829-求形如UVU的串的个数】后缀数组+rmq or 直接for水过
【uva10829-求形如UVU的串的个数】后缀数组+rmq or 直接for水过
题意：UVU形式的串的个数，V的长度规定，U要一样，位置不同即为不同字串
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1770
题解：一开始理解错题意，以为是abcxxxcba(xxx为v)，开心地打了后缀数组后发现哎样例不对丫。。
UVA的意思是abcxxxabc(xxx为v)。
类似poj3693，我们暴力枚举U的长度L，对原串按U的长度进行分块。
对于当前分块出来的点x，y=x+u+v是UVU中后一个U中的对应点。
然后往前往后匹配：这里其实是应该用后缀数组+rmq匹配的，然而我用for循环直接暴 过了。。
然后我们得到了两条串的往前往后的lcp1和lcp2。（往前往后都只用匹配L就够了，不然会在下一个分割点找到）
ans+=lcp1+lcp2-L
减L的原因：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<queue> 6 using namespace std; 7 8 typedef long long LL; 9 const int N=100010;10 int sl,cl,v;11 char c[N];12 13 int main()14 {15 freopen("a.in","r",stdin);16 freopen("me.out","w",stdout);17 int T,cas=0;18 scanf("%d",&T);19 while(T--)20 {21 scanf("%d",&v);22 scanf("%s",c+1);23 cl=sl=strlen(c+1);24 int x,y,now;25 LL t0,t1,ans=0;26 for(int L=1;L<=cl;L++) 27 {28 for(int i=0;(i*L)<=cl;i++)29 {30 x=i*L+1,y=((i+1)*L)+v+1;31 if(y>cl) break;32 t0=t1=0;33 for(int j=0;j<L;j++)34 {35 if(c[x-j]!=c[y-j] || x-j<1) break;36 t0++;37 }38 for(int j=0;j<L;j++) 39 {40 if(c[x+j]!=c[y+j] || y+j>cl) break;41 t1++;42 }43 if(t0 && t1 && t0+t1>=L) ans+=t1+t0-L;44 }45 }46 printf("Case %d: %lld\n",++cas,ans);47 }48 return 0;49 }
【uva10829-求形如UVU的串的个数】后缀数组+rmq or 直接for水过
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。