专栏首页ACM算法日常String Problem(KMP+最小表示法)- HDU 3374

String Problem(KMP+最小表示法)- HDU 3374

Problem Description

Give you a string with length N, you can generate N strings by left shifts. For example let consider the string “SKYLONG”, we can generate seven strings: String Rank SKYLONG 1 KYLONGS 2 YLONGSK 3 LONGSKY 4 ONGSKYL 5 NGSKYLO 6 GSKYLON 7 and lexicographically first of them is GSKYLON, lexicographically last is YLONGSK, both of them appear only once. Your task is easy, calculate the lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), its times, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.

Input

Each line contains one line the string S with length N (N <= 1000000) formed by lower case letters.

Output

Output four integers separated by one space, lexicographically fisrt string’s Rank (if there are multiple answers, choose the smallest one), the string’s times in the N generated strings, lexicographically last string’s Rank (if there are multiple answers, choose the smallest one), and its times also.

Sample Input

abcder
aaaaaa
ababab

Sample Output

1 1 6 1
1 6 1 6
1 3 2 3

概译:一个字符串循环一下,每个位置都当一次头(即循环同构),求最小和最大字典序的那两个串的起始位置和总共出现次数。译的不好,不过原文其实很好懂。

输出:最小字典序的rank,出现次数,最大字典序的rank,出现次数

求rank是典型的用最小表示法来求,而求出现的次数是循环节的次数,没有循环节就1次呗。求循环节需要使用到kmp算法中next数组的递推过程。

至于kmp算法和最小表示法,都是字符串的相关算法。个人感觉讲起来是很难懂的,不懂的同学希望能够自学一下,按照博客上的思路及代码自己画一画会好很多。这道题目和这两个算法,AlphaWA也是听了大佬的讲课介绍然后新学的(被校友认出系列),刚开始肯定感觉不透彻,不熟悉原理,不过以后慢慢变强了就会加深理解了吧,学习的过程好像一般都是这样子的(我胡扯的)。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1000010
using namespace std;

char s[maxn];
int Next[maxn];

void getnext(char *s,int len)//求next数组以获得循环节长度 
{
    Next[0]=Next[1]=0;
    for(int i=1;i<len;i++)
    {
        int j=Next[i];
        while(j&&s[i]!=s[j]) j=Next[j];
        Next[i+1]=s[i]==s[j]?j+1:0;
    }
}

int express(char *s,int len,int flag)//最小表示法求最小字典序的循环同构的起始位置 
{
    int i=0,j=1,k=0;
    while(i<len&&j<len&&k<len)
    {
        int t=s[(i+k)%len]-s[(j+k)%len];
        if(flag)//最小表示 
        {
            if(!t) k++;
            else if(t>0) i=i+k+1,k=0;
            else j=j+k+1,k=0;
            if(i==j) j++;
        }
        else//最大表示 
        {
            if(!t) k++;
            else if(t<0) i=i+k+1,k=0;
            else j=j+k+1,k=0;
            if(i==j) j++;   
        }
    }
    return min(i,j);
}

int main()
{
    while(~scanf("%s",s))
    {
        int len=strlen(s);
        int rank1=express(s,len,1)+1,rank2=express(s,len,0)+1;//flag设为1是求最小字典序,设为0是求最大 
        getnext(s,len);//kmp里面求next数组的方法 
        int cnt=len/(len-Next[len]);//据说个数就是循环节的个数,最大最小都是一样的 
        printf("%d %d %d %d\n",rank1,cnt,rank2,cnt);
    }
    return 0;
} 

本文分享自微信公众号 - ACM算法日常(acm-clan),作者:AlphaWA

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2018-05-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU6370:Werewolf 推理+拓扑排序 2018第六场杭电多校

    "The Werewolves" is a popular card game among young people.In the basic game, th...

    ACM算法日常
  • 牛客小白月赛11D(分治、RMQ)

    定义一个玄学节点叫做 R,每次操作读入 val ,执行 Insert(R,val)。

    ACM算法日常
  • #633 DIV2 题解

    组样例,每组样例给一个, 代表个三角形按照菱形的样子尽可能的拼凑在一起(可以旋转),如图所示

    ACM算法日常
  • ZOJ 3490 String Successor(模拟)

    Time Limit: 2 Seconds Memory Limit: 65536 KB The successor to a string ca...

    ShenduCC
  • HDU----(3294)Girls' research(manacher)

    Girls' research Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 65535/3...

    Gxjun
  • 【USACO 1.5】Prime Palindromes

    饶文津
  • HDU 4247 Pinball Game 3D(cdq 分治+树状数组+动态规划)

    Pinball Game 3D Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/...

    ShenduCC
  • 11-散列2 Hashing (25分)

    The task of this problem is simple: insert a sequence of distinct positive integ...

    AI那点小事
  • 算法复杂度O(logn)详解

    由于cnt每次在乘以2之后都会更加逼近n,也就是说,在有x次后,cnt将会大于n从而跳出循环,所以

    233333
  • 桶排序的算法

    思路:设数组的长度为len,创建三个长度为len+1的(桶)数组。将数组的元素根据大小放在不同的桶中,其中,必定有差值大于一个桶的差存在,故同一个桶中不可能出现...

    曼路

扫码关注云+社区

领取腾讯云代金券