您的位置:68399皇家赌场 > 集群主机 > [xjoi1898] [hdu4333]Revolving Digits,xjoi1898hdu4333

[xjoi1898] [hdu4333]Revolving Digits,xjoi1898hdu4333

发布时间:2019-08-24 10:33编辑:集群主机浏览(155)

    [xjoi1898] [hdu4333]Revolving Digits,xjoi1898hdu4333

    /*留意留意:本题非hdu4333原题,而是简化版,原版有多组数据。但此代码在修改输入后还是能因而多组数据*/

     

    付给贰个数字串,问有稍许本质不一样同构串比原串小,同样,大.
    同构串是指,对于原串S[1-N]透过旋转换成同构串S[i-N] S[0-i-1].
    本质区别,指的是字符串不一样样.

    /*注意小心:本题非hdu4333原题,而是简化版,原版有多组数据。但此代码在改造输入后还是能够经过多组数据*/

    /*小心留意:本题非hdu4333原题,而是简化版,原版有多组数据。但此代码在修改输入后还是可以由此多组数据*/

    1、HDU 1711 Number Sequence

    输入格式:

    一行贰个数字串

     

    交由一个数字串,问有多少本质分歧同构串比原串小,同样,大.
    同构串是指,对于原串S[1-N]通过旋调换成同构串S[i-N] S[0-i-1].
    真相分裂,指的是字符串区别.

      题意:给出七个数字串a,b,问能还是不能够使得数字串b为a的子串,能则输出最小的合作岗位。

    出口格式:

    一行,输出本质不一样的同构串比原串小,同样,大的多个数,用二个空格分隔绝。

    交给一个数字串,问有多少本质不相同同构串比原串小,同样,大.
    同构串是指,对于原串S[1-N]通过旋调换成同构串S[i-N] S[0-i-1].
    真相差别,指的是字符串不一致样.

    输入格式:

    一行二个数字串

      思路:KMP模板题

    样例输入:

    123123
    

    输入格式:

    一行一个数字串

    输出格式:

    一行,输出本质差别的同构串比原串小,同样,大的四个数,用三个空格分隔断。

    图片 1图片 2

    样例输出:

    0 1 2
    

    输出格式:

    一行,输出本质不一样的同构串比原串小,一样,大的八个数,用叁个空格分隔离。

    样例输入:

    123123
    
     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 const int maxn = 1000010;
     5 const int maxm = 10010;
     6 int p[maxm];
     7 int des[maxn];
     8 int Next[maxm];
     9 int n, m;
    10 void GetNext(int *next, int *src, int len)
    11 {//next和src都从下标1开始存储
    12     next[1] = 0;
    13     int j = 1, i = 0;
    14     while (j <= len)
    15     {
    16         if (i == 0 || src[j] == src[i])
    17         {
    18             j  ;
    19             i  ;
    20             next[j] = i;
    21         }
    22         else i = next[i];
    23     }
    24 }
    25 
    26 int KMP(int *T, int *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
    27 {
    28     int lenT = n;
    29     int lenP = m;
    30     int posT = 1, posP = 1;
    31     while (posP <= lenP&&posT <= lenT)
    32     {
    33         if (posP == 0 || T[posT] == P[posP])
    34         {
    35               posT;
    36               posP;
    37         }
    38         else posP = next[posP];
    39     }
    40     if (posP <= lenP) return -1;
    41     else return posT - lenP;
    42 }
    43 int main()
    44 {
    45     int t;
    46     scanf("%d", &t);
    47 
    48     while (t--)
    49     {
    50         scanf("%d%d", &n, &m);
    51         for (int i = 1; i <= n; i  ) scanf("%d", &des[i]);
    52         for (int i = 1; i <= m; i  ) scanf("%d", &p[i]);
    53         GetNext(Next, p, m);
    54         printf("%dn", KMP(des, p, Next));
    55     }
    56     return 0;
    57 }
    

    多少范围:

    数字串长度<=一千00         首先,大家用KMP求得KMP中的next数组nex,那有怎么样用呢?其功用在于求出原字符串的循环节个数,以此保险计数的字符串本质不一致然后,设原字符串为s2,字符串s1=s2 s2。以s1为母串,s2为子串跑EKMP。 最终,对于每贰个ex[i],大于等于s2的长短即从第i个任务上马的构成的数与原数相等,否则假若相比较s[i]与s[i next[i]](EKMP的next)。    

    #include<cstdio>
    #include<cstring>
    using namespace std;
    char s1[1000100],s2[1000100];
    int ex[1000100],nxt[1000100],nex[1000100];
    void get(char *s2){
        int m=strlen(s2);
        nex[0]=nex[1]=0;int j=0;
        for(int i=1;i<m;i  ){
            while(j>0&&s2[i]!=s2[j])j=nex[j];
            if(s2[i]==s2[j])j  ;
            nex[i 1]=j;
        }
    }
    void getex(char *s2){
        int j=0,n=strlen(s2);
        while(j 1<n&&s2[j 1]==s2[j])j  ;
        nxt[0]=n;nxt[1]=j;int po=1,p=nxt[1] 1;
        for(int i=2;i<n;i  ){
            int len=nxt[i-po];
            if(len i<p)nxt[i]=len;
            else{
                int j=p-i;
                if(j<0)j=0;
                while(i j<n&&s2[j]==s2[j i])j  ;
                nxt[i]=j;
                po=i;
                p=nxt[po] po;
            }
        }
    }
    void exkmp(char *s1,char *s2){
        int j=0,n=strlen(s1),m=strlen(s2);
        while(s1[j]==s2[j]&&j<n&&j<m)j  ;
        ex[0]=j;int po=0,p=ex[0];
        for(int i=1;i<n;i  ){
            int len=nxt[i-po];
            if(len i<p)ex[i]=len;
            else{
                int j=p-i;
                while(i j<n&&j<m&&s1[j i]==s2[j])j  ;
                ex[i]=j;
                po=i;
                p=ex[po] po;
            }
        }
    }
    int main(){
        scanf("%s",s2);int len=strlen(s2);
        for(int i=0;i<len;i  )
        s1[i]=s2[i],s1[i len]=s2[i];
        getex(s2);
        exkmp(s1,s2);
        get(s2);
    
        int temp=len%(len-nex[len])==0?len/(len-nex[len]):1;
        int a=0,b=0,c=0;
        for(int i=0;i<len;i  ){
            if(ex[i]>=len)b  ;
            else if(s1[i ex[i]]<s2[ex[i]])a  ;
            else c  ;
        }
        printf("%d %d %d",a/temp,b/temp,c/temp);
    }
    

     

    ] [hdu4333]Revolving Digits,xjoi1898hdu4333 /*只顾小心:本题非hdu4333原题,而是简化版,原版有多组数据。但此代码在改造输入后如故能够通...

    样例输入:

    123123
    

    样例输出:

    0 1 2
    

    View Code

    样例输出:

    0 1 2
    

    数量范围:

    数字串长度<=一千00率先,大家用KMP求得KMP中的next数组nex,那有啥样用吧?其意义在于求出原字符串的循环节个数,以此保险计数的字符串本质不相同然后,设原字符串为s2,字符串s1=s2 s2。以s1为母串,s2为子串跑EKMP。最后,对于每三个ex[i],大于等于s2的长短即从第i个岗位上马的组成的数与原数相等,不然一旦相比较s[i]与s[i next[i]](EKMP的next)。

    #include<cstdio>#include<cstring>using namespace std;char s1[1000100],s2[1000100];int ex[1000100],nxt[1000100],nex[1000100];void get(char *s2){    int m=strlen;    nex[0]=nex[1]=0;int j=0;    for(int i=1;i<m;i  ){        while(j>0&&s2[i]!=s2[j])j=nex[j];        if(s2[i]==s2[j])j  ;        nex[i 1]=j;    }}void getex(char *s2){    int j=0,n=strlen;    while(j 1<n&&s2[j 1]==s2[j])j  ;    nxt[0]=n;nxt[1]=j;int po=1,p=nxt[1] 1;    for(int i=2;i<n;i  ){        int len=nxt[i-po];        if(len i<p)nxt[i]=len;        else{            int j=p-i;            if(j<0)j=0;            while(i j<n&&s2[j]==s2[j i])j  ;            nxt[i]=j;            po=i;            p=nxt[po] po;        }    }}void exkmp(char *s1,char *s2){    int j=0,n=strlen,m=strlen;    while(s1[j]==s2[j]&&j<n&&j<m)j  ;    ex[0]=j;int po=0,p=ex[0];    for(int i=1;i<n;i  ){        int len=nxt[i-po];        if(len i<p)ex[i]=len;        else{            int j=p-i;            while(i j<n&&j<m&&s1[j i]==s2[j])j  ;            ex[i]=j;            po=i;            p=ex[po] po;        }    }}int main(){    scanf("%s",s2);int len=strlen;    for(int i=0;i<len;i  )    s1[i]=s2[i],s1[i len]=s2[i];    getex;    exkmp;    get;        int temp=len%(len-nex[len])==0?len/(len-nex[len]):1;    int a=0,b=0,c=0;    for(int i=0;i<len;i  ){        if(ex[i]>=len)b  ;        else if(s1[i ex[i]]<s2[ex[i]])a  ;        else c  ;    }    printf("%d %d %d",a/temp,b/temp,c/temp);}
    

    2、HDU 1686 Oulipo

    多少范围:

    数字串长度<=一千00

     

     

     

     

    先是,大家用KMP求得KMP中的next数组nex,那有啥用吗?其功能在于求出原字符串的循环节个数,以此保险计数的字符串本质分歧

    然后,设原字符串为s2,字符串s1=s2 s2。以s1为母串,s2为子串跑EKMP。

    末了,对于每叁个ex[i],大于等于s2的长短即从第i个职责上马的整合的数与原数相等,不然假若相比较s[i]与s[i next[i]](EKMP的next)。

     

     

    #include<cstdio>
    #include<cstring>
    using namespace std;
    char s1[1000100],s2[1000100];
    int ex[1000100],nxt[1000100],nex[1000100];
    void get(char *s2){
        int m=strlen(s2);
        nex[0]=nex[1]=0;int j=0;
        for(int i=1;i<m;i  ){
            while(j>0&&s2[i]!=s2[j])j=nex[j];
            if(s2[i]==s2[j])j  ;
            nex[i 1]=j;
        }
    }
    void getex(char *s2){
        int j=0,n=strlen(s2);
        while(j 1<n&&s2[j 1]==s2[j])j  ;
        nxt[0]=n;nxt[1]=j;int po=1,p=nxt[1] 1;
        for(int i=2;i<n;i  ){
            int len=nxt[i-po];
            if(len i<p)nxt[i]=len;
            else{
                int j=p-i;
                if(j<0)j=0;
                while(i j<n&&s2[j]==s2[j i])j  ;
                nxt[i]=j;
                po=i;
                p=nxt[po] po;
            }
        }
    }
    void exkmp(char *s1,char *s2){
        int j=0,n=strlen(s1),m=strlen(s2);
        while(s1[j]==s2[j]&&j<n&&j<m)j  ;
        ex[0]=j;int po=0,p=ex[0];
        for(int i=1;i<n;i  ){
            int len=nxt[i-po];
            if(len i<p)ex[i]=len;
            else{
                int j=p-i;
                while(i j<n&&j<m&&s1[j i]==s2[j])j  ;
                ex[i]=j;
                po=i;
                p=ex[po] po;
            }
        }
    }
    int main(){
        scanf("%s",s2);int len=strlen(s2);
        for(int i=0;i<len;i  )
        s1[i]=s2[i],s1[i len]=s2[i];
        getex(s2);
        exkmp(s1,s2);
        get(s2);
    
        int temp=len%(len-nex[len])==0?len/(len-nex[len]):1;
        int a=0,b=0,c=0;
        for(int i=0;i<len;i  ){
            if(ex[i]>=len)b  ;
            else if(s1[i ex[i]]<s2[ex[i]])a  ;
            else c  ;
        }
        printf("%d %d %d",a/temp,b/temp,c/temp);
    }
    

     

     

     

     

     

     

     

     

     

      题意:给出情势串p,文本串t,求p在t中冒出的次数(可重叠)

      思路:KMP同一时间记录相称的个数。

    图片 3图片 4

     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 const int maxn = 1000100;
     5 const int maxp = 10010;
     6 char t[maxn];
     7 char p[maxp];
     8 int Next[maxp];
     9 void GetNext(int *next, char *src, int len)
    10 {//next和src都从下标0开始存储
    11     next[0] = -1;
    12     int j = 0, i = -1;
    13     while (j < len)
    14     {
    15         if (i == -1 || src[j] == src[i])
    16         {
    17             j  ;
    18             i  ;
    19             next[j] = i;
    20         }
    21         else i = next[i];
    22     }
    23 }
    24 
    25 int KMP(char*T, char *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
    26 {
    27     int lenT = strlen(T);
    28     int lenP = strlen(P);
    29     int posT = 0, posP = 0;
    30     int cnt = 0;
    31     while (posT <lenT)
    32     {
    33         if (posP == -1 || T[posT] == P[posP])
    34         {
    35               posT;
    36               posP;
    37         }
    38         else posP = next[posP];
    39         if (posP== lenP)
    40         {
    41             cnt  ;
    42             posP = next[posP];
    43         }
    44     }
    45     return cnt;
    46 }
    47 int main()
    48 {
    49     int Case;
    50     scanf("%d", &Case);
    51     while (Case--)
    52     {
    53         scanf("%s", p);
    54         scanf("%s", t);
    55         GetNext(Next, p, strlen(p));
    56         printf("%dn", KMP(t,p, Next));
    57     }
    58     return 0;
    59 }
    

    View Code

    3、hdu 2087 剪花布条

      题意:给出a串和b串,求b串在a串中冒出的次数(不可重叠)

      思路:KMP。注意更新指针时和上一题的不及。

    图片 5图片 6

     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 const int maxn = 1010;
     5 const int maxp = 1010;
     6 char t[maxn];
     7 char p[maxp];
     8 int Next[maxp];
     9 void GetNext(int *next, char *src, int len)
    10 {//next和src都从下标0开始存储
    11     next[0] = -1;
    12     int j = 0, i = -1;
    13     while (j < len)
    14     {
    15         if (i == -1 || src[j] == src[i])
    16         {
    17             j  ;
    18             i  ;
    19             next[j] = i;
    20         }
    21         else i = next[i];
    22     }
    23 }
    24 
    25 int KMP(char*T, char *P, int *next)//在目标串T中从位置1开始查找模式串P第一次出现的位置
    26 {
    27     int lenT = strlen(T);
    28     int lenP = strlen(P);
    29     int posT = 0, posP = 0;
    30     int cnt = 0;
    31     while (posT <lenT)
    32     {
    33         if (posP == -1 || T[posT] == P[posP])
    34         {
    35               posT;
    36               posP;
    37         }
    38         else posP = next[posP];
    39         if (posP == lenP)
    40         {
    41             cnt  ;
    42             posP  ;
    43         }
    44     }
    45     return cnt;
    46 }
    47 int main()
    48 {
    49     while (~scanf("%s",&t))
    50     {
    51         if (t[0] == '#')break;
    52         scanf("%s", p);
    53         GetNext(Next, p, strlen(p));
    54         printf("%dn", KMP(t, p, Next));
    55     }
    56     return 0;
    57 }
    

    View Code

     4、HDU 3746 Cyclic Nacklace

      题意:求最少在最终补多少个字符技能使得此串产生循环.

      思路:lenB%(lenB-Next[lenB])==0则其有周期lenB/(lenB-Next[lenB]),当中异常的小循环节长度是lenB-Next[lenB]。

    图片 7图片 8

     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 const int maxn = 100010;
     5 const int maxp = 100010;
     6 char t[maxn];
     7 char p[maxp];
     8 int Next[maxp];
     9 void GetNext(int *next, char *src, int len)
    10 {//next和src都从下标0开始存储
    11     next[0] = -1;
    12     int j = 0, i = -1;
    13     while (j < len)
    14     {
    15         if (i == -1 || src[j] == src[i])
    16         {
    17             j  ;
    18             i  ;
    19             next[j] = i;
    20         }
    21         else i = next[i];
    22     }
    23 }
    24 int main()
    25 {
    26     int C;
    27     scanf("%d", &C);
    28     while (C--)
    29     {
    30         scanf("%s", &t);
    31         int ll = strlen(t);
    32         GetNext(Next, t,ll);
    33         int len = ll - Next[ll];//循环节长度
    34         if (len != ll&&ll%len == 0) printf("0n");
    35         else printf("%dn", len - Next[ll] % len);
    36     }
    37     return 0;
    38 }
    

    View Code

    5、POJ 1961 Period

      题意:求出母串的富有前缀的循环节大于1的循环串。

      思路:依照next数组的习性即 i-next[i] 为八个循环节的尺寸。

    图片 9图片 10

     1 #include<iostream>
     2 #include<cstring>
     3 using namespace std;
     4 const int maxn = 1000010;
     5 char des[maxn];
     6 int Next[maxn];
     7 int n, Case;
     8 void GetNext(int *next, char *src, int len)
     9 {
    10     next[0] = -1;
    11     int j = 0, i = -1;
    12     while (j <len)
    13     {
    14         if (i == -1 || src[j] == src[i])
    15         {
    16             j  ;
    17             i  ;
    18             next[j] = i;
    19         }
    20         else i = next[i];
    21     }
    22 }
    23 void Solve()
    24 {
    25     printf("Test case #%dn", Case  );
    26     for (int i = 1; i <= n; i  )
    27     {
    28         int len = i - Next[i];
    29         if (i!= len && i % len == 0)
    30         {
    31             printf("%d %dn", i, i / len);
    32         }
    33     }
    34     printf("n");
    35 }
    36 int main()
    37 {
    38     Case = 1;
    39     while (~scanf("%d", &n) && n)
    40     {
    41         scanf("%s", des);
    42         GetNext(Next, des, n);
    43         Solve();
    44     }
    45     return 0;
    46 }
    

    View Code

    6、HUST 1010 The Minimum Length

      题意:有七个字符串A,一回次的重写A,会博得四个新的字符串AAAAAAAA.....,以往将那些字符串从中切去一部分收获四个字符串B,比如有三个字符串A="abcdefg".,复制五回现在得到abcdefgabcdefgabcdefgabcdefg....,今后切取一有的,获得字符串B,未来只交给字符串B,求出字符串A的长短。

      思路:最小的循环节:len-next[len]。

    本文由68399皇家赌场发布于集群主机,转载请注明出处:[xjoi1898] [hdu4333]Revolving Digits,xjoi1898hdu4333

    关键词: 68399皇家赌场 Revolving Digits ACM萌动之旅 KMP