【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的原因：

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<queue>

 using namespace std;

 typedef long long LL;

 const int N=;

 int sl,cl,v;

 char c[N];

 int main()

 {

     freopen("a.in","r",stdin);

     freopen("me.out","w",stdout);

     int T,cas=;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%d",&v);

         scanf("%s",c+);

         cl=sl=strlen(c+);

         int x,y,now;

         LL t0,t1,ans=;

         for(int L=;L<=cl;L++)

         {

             for(int i=;(i*L)<=cl;i++)

             {

                 x=i*L+,y=((i+)*L)+v+;

                 if(y>cl) break;

                 t0=t1=;

                 for(int j=;j<L;j++)

                 {

                     if(c[x-j]!=c[y-j] || x-j<) break;

                     t0++;

                 }

                 for(int j=;j<L;j++)

                 {

                     if(c[x+j]!=c[y+j] || y+j>cl) break;

                     t1++;

                 }

                 if(t0 && t1 && t0+t1>=L) ans+=t1+t0-L;

             }

         }

         printf("Case %d: %lld\n",++cas,ans);

     }

     return ;

 }

巴特西

【uva10829-求形如UVU的串的个数】后缀数组+rmq or 直接for水过

最新文章

热门文章