bzoj2740 串 && bzoj2176 strange string(最小表示法模板)

https://konnyakuxzy.github.io/BZPRO/JudgeOnline/2740.html

题解讲的很清楚了

（好像等于的情况应该归入case2而不是case1？并不确定）

具体方法：

将串翻转，找到字典序最小且最短的后缀，然后找到以这个后缀为纯循环节的最长后缀T，则第一步是将这个后缀T提到最前面；

然后第二步是把整个串除T外部分变为其循环同构串的最小表示。

要找到字典序最小且最短的后缀，只要找到整个串的最小表示法（设最小表示法在位置i开始），然后找到S[i..n]的最短公共前后缀即可（容易发现是对的）（见代码1）；也可以直接用最小表示法类似的方法一次直接求出来（见代码2）

代码1：

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int T;

 char s[];

 int f[];

 int calc(const char *s,int n)

 {

     int i=,j=,k=,t;

     while(i<n&&j<n&&k<n)

     {

         t=s[(i+k)%n]-s[(j+k)%n];

         if(t==)    ++k;

         else

         {

             if(t>)    i+=k+;

             else    j+=k+;

             if(i==j)    ++j;

             k=;

         }

     }

     return min(i,j);

 }

 int n;

 int an1,an2;

 int main()

 {

     int i,j,t;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%s",s);n=strlen(s);

         reverse(s,s+n);

         t=calc(s,n);

         //printf("1t%d\n",t);

         //t=0;

         f[t]=;

         for(i=t+,j=;i<n;++i)

         {

             //j=f[i-1];

             while(j>&&s[t+j]!=s[i])    j=f[t+j-];

             //printf("2t%d %c %c\n",j,s[t+j],s[i]);

             if(s[t+j]==s[i])    ++j;

             //printf("1t%d %d %d\n",i,t+j,s[t+j]==s[i]);

             f[i]=j;

         }

         //for(i=t;i<n;++i)    printf("%d %d\n",i,f[i]);

         j=f[n-];

         if(j)

         {

             while(f[t+j-]>)    j=f[t+j-];

             t=n-j;

         }

         //printf("1t%d\n",t);

         for(j=t;;)

         {

             //printf("3t%d %d\n",j-(n-t),t);

             if(j>=n-t&&strncmp(s+(j-(n-t)),s+t,n-t)==)

                 j-=n-t;

             else

                 break;

         }

         t=j;

         //printf("2t%d\n",t);

         an1=n-t;

         //printf("%d\n",an1);

         //printf("%d\n",t);

         t=calc(s,t);

         an2=n-t;

         printf("%d %d\n",an1,an2);

     }

     return ;

 }

代码2：（话说这个复杂度真的对吗？不确定啊？不过实测全a串还有一些随机的串的确是O(n)的，并且能A掉题）

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int T;

 char s[];

 //int f[10000100];

 int calc(const char *s,int n)

 {

     int i=,j=,k=,t;

     while(i<n&&j<n&&k<n)

     {

         t=s[(i+k)%n]-s[(j+k)%n];

         if(t==)    ++k;

         else

         {

             if(t>)    i+=k+;

             else    j+=k+;

             if(i==j)    ++j;

             k=;

         }

     }

     return min(i,j);

 }

 int n;

 int an1,an2;

 int main()

 {

     int i,j,k,t;

     scanf("%d",&T);

     while(T--)

     {

         scanf("%s",s);

         n=strlen(s);

         reverse(s,s+n);

         i=;j=;k=;

         //int tt=0;

         while(i<n&&j<n&&k<n)

         {

             //++tt;

             //printf("1t%d %d %d\n",i,j,k);

             t=((i+k<n)?s[i+k]:)-((j+k<n)?s[j+k]:);

             if(t==)    ++k;

             else

             {

                 if(t>)    i+=(j+k<n)?k+:k;

                 else    j+=(i+k<n)?k+:k;

                 if(i==j)    ++j;

                 k=;

             }

         }

         //printf("1t%d\n",tt);

         t=min(i,j);

         for(j=t;;)

         {

             if(j>=n-t&&strncmp(s+(j-(n-t)),s+t,n-t)==)

                 j-=n-t;

             else

                 break;

         }

         t=j;

         an1=n-t;

         t=calc(s,t);

         an2=n-t;

         printf("%d %d\n",an1,an2);

     }

     return ;

 }

https://konnyakuxzy.github.io/BZPRO/JudgeOnline/2176.html

最小表示法板子

题解

这题数据范围比较诡异，一定要用unsigned char。。。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 unsigned char s[];

 int calc(const unsigned char *s,int n)

 {

     int i=,j=,k=,t;

     while(i<n&&j<n&&k<n)

     {

         t=s[(i+k)%n]-s[(j+k)%n];

         if(t==)    ++k;

         else

         {

             if(t>)    i+=k+;

             else    j+=k+;

             if(i==j)    ++j;

             k=;

         }

     }

     return min(i,j);

 }

 int n;

 int main()

 {

     int t;

     scanf("%d%s",&n,s);

     t=calc(s,n);

     printf("%s",s+t);

     s[t]=;

     printf("%s",s);

     return ;

 }

巴特西

bzoj2740 串 && bzoj2176 strange string(最小表示法模板)

最新文章

热门文章