首页 / GIT / HDU 4333 Revolving Digits [扩展KMP]【学习笔记】

HDU 4333 Revolving Digits [扩展KMP]【学习笔记】

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU 4333 Revolving Digits [扩展KMP]【学习笔记】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2618字，纯文字阅读大概需要4分钟。

内容图文

题意：给一个数字，每一次把它的最后一位拿到最前面，一直那样下去，分别求形成的数字小于，等于和大于原来数的个数。

 

SAM乱搞失败

当然要先变SS了

然后考虑每个后缀前长为n个字符，把它跟S比较就行了

如果用后缀家族的话复杂度要加上log，本题会TLE吧

求一个串S的每个后缀与另一个串T的最长公共前缀可以用扩展KMP！复杂度O(n+m)

看课件吧 

 

从1开始写真不容易以后再也不从1开始了，判断位置好麻烦好容易错

next[i]=LCP(T[i,m],T)

extend[i]=LCP(S[i,n],T)

主要思想就是求i时记录p=max{a+extend[a]-1},1<=a<i 也就是当前最远匹配到哪里，这么做是为了以后直接利用next的信息

S[a,a+extend[a]-1]--->T[1,extend[a]-1]是一样的

那么从i开始的后缀的前一部分是和T[i-a+1..]相同的，就不用比较了因为已经有L=next[i-a+1]了

如果i+L-1<p，extend[i]=L

否则从s[p+1]和t[p-i+1+1]开始暴力往后匹配，并更新a

 

注意：本题要求不相同的数字，出现相同数字说明有循环节，KMP求一下看看有没有可以整除的循环节

 

#include <cstdio>
#include <cstring>
usingnamespace std;
constint N=2e6+5;
inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}
    return x*f;
}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int n,m;
int next[N],extend[N];
char s[N],t[N];
void getNext(char s[],int n){
    //printf("getNext %d\n",n);
    //for(int i=1;i<=n;i++) printf("%c",s[i]);
    next[1]=n;
    int a=1;
    while(a<n&&s[a]==s[a+1]) a++;
    next[2]=a-1;
    a=2;
    for(int i=3;i<=n;i++){
        int p=a+next[a]-1,L=next[i-a+1];
        if(i+L-1<p) next[i]=L;
        else{
            int j=max(p-i+1,0);//!!while(i+j<=n&&s[i+j]==s[j+1]) j++;
            next[i]=j;a=i;
        }
    }
    //for(int i=1;i<=n;i++) printf("next %d %d\n",i,next[i]);}    
void getExtend(char s[],char t[]){
    //printf("getExtend %d\n",n);
    //for(int i=1;i<=n;i++) printf("%c",s[i]);puts("");    getNext(t,m);
    int mn=min(n,m),a=1;
    while(a<=mn&&s[a]==t[a]) a++;
    extend[1]=a-1;
    a=1;
    for(int i=2;i<=n;i++){
        int p=a+extend[a]-1,L=next[i-a+1];
        if(i+L-1<p) extend[i]=L;
        else{
            int j=max(p-i+1,0);
            while(i+j<=n&&s[i+j]==t[j+1]) j++;
            extend[i]=j;
            a=i;
        }
    }
    //for(int i=1;i<=n;i++) printf("extend %d %d\n",i,extend[i]);}
int fail[N];
void getFail(char s[],int n){
    fail[1]=0;
    for(int i=2;i<=n;i++){
        int j=fail[i-1];
        while(j&&s[j+1]!=s[i]) j=fail[j];
        fail[i]=s[j+1]==s[i]?j+1:0;
    }
}
int L,E,G;
void solve(){
    getExtend(s,t);
    L=E=G=0;
    for(int i=1;i<=m;i++){
        int lcp=extend[i];
        if(lcp>=m) E++;
        elseif(t[1+lcp]<s[i+lcp]) G++;
        else L++;
    }
//for(int i=1;i<=n;i++) printf("hi %d %d %d\n",i,next[i],extend[i]);    getFail(t,m);
    int _=m%(m-fail[m])==0?m/(m-fail[m]):1;
    L/=_;E/=_;G/=_;
}

int main(){
    freopen("in","r",stdin);
    int T=read(),cas=0;
    while(T--){
        scanf("%s",s+1);
        n=m=strlen(s+1);
        for(int i=1;i<=n;i++) s[i+n]=t[i]=s[i];
        n<<=1;
        solve();
        printf("Case %d: %d %d %d\n",++cas,L,E,G);
    }
}

 

原文：http://www.cnblogs.com/candy99/p/6395066.html

内容总结

以上是互联网集市为您收集整理的HDU 4333 Revolving Digits [扩展KMP]【学习笔记】全部内容，希望文章能够帮你解决HDU 4333 Revolving Digits [扩展KMP]【学习笔记】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1255387.html

来源：【匿名】