POJ 1509 Glass Beads

POJ 1509 Glass Beads

大家好,又见面了,我是全栈君,祝每个程序员都可以多学几门语言。

后缀自己主动机的简单运用….

Glass Beads
Time Limit: 3000MS   Memory Limit: 10000K
Total Submissions: 2352   Accepted: 1375

Description

Once upon a time there was a famous actress. As you may expect, she played mostly Antique Comedies most of all. All the people loved her. But she was not interested in the crowds. Her big hobby were beads of any kind. Many bead makers were working for her and they manufactured new necklaces and bracelets every day. One day she called her main Inspector of Bead Makers (IBM) and told him she wanted a very long and special necklace. 

The necklace should be made of glass beads of different sizes connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not very robust so it is possible that the necklace will get torn by its own weight. The situation becomes even worse when the necklace is disjoined. Moreover, the point of disconnection is very important. If there are small beads at the beginning, the possibility of tearing is much higher than if there were large beads. IBM wants to test the robustness of a necklace so he needs a program that will be able to determine the worst possible point of disjoining the beads. 

The description of the necklace is a string A = a1a2 … am specifying sizes of the particular beads, where the last character am is considered to precede character a1 in circular fashion. 

The disjoint point i is said to be worse than the disjoint point j if and only if the string aiai+1 … ana1 … ai-1 is lexicografically smaller than the string ajaj+1 … ana1 … aj-1. String a1a2 … an is lexicografically smaller than the string b1b2 … bn if and only if there exists an integer i, i <= n, so that aj=bj, for each j, 1 <= j < i and ai < bi

Input

The input consists of N cases. The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line containing necklace description. Maximal length of each description is 10000 characters. Each bead is represented by a lower-case character of the english alphabet (a–z), where a < b … z.

Output

For each case, print exactly one line containing only one integer — number of the bead which is the first at the worst possible disjoining, i.e.\ such i, that the string A[i] is lexicographically smallest among all the n possible disjoinings of a necklace. If there are more than one solution, print the one with the lowest i.

Sample Input

4
helloworld
amandamanda
dontcallmebfu
aaabaaa

Sample Output

10
11
6
5

Source

[Submit]   [Go Back]   [Status]   [Discuss]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int CHAR=26,maxn=50000;

struct SAM_Node
{
    SAM_Node *fa,*next[CHAR];
    int len,id,pos;
    SAM_Node(){}
    SAM_Node(int _len)
    {
        fa=0; len=_len;
        memset(next,0,sizeof(next));
    }
};

SAM_Node SAM_node[maxn],*SAM_root,*SAM_last;
int SAM_size;

SAM_Node *newSAM_Node(int len)
{
    SAM_node[SAM_size]=SAM_Node(len);
    SAM_node[SAM_size].id=SAM_size;
    return &SAM_node[SAM_size++];
}

SAM_Node *newSAM_Node(SAM_Node *p)
{
    SAM_node[SAM_size]=*p;
    SAM_node[SAM_size].id=SAM_size;
    return &SAM_node[SAM_size++];
}

void SAM_init()
{
    SAM_size=0;
    SAM_root=SAM_last=newSAM_Node(0);
    SAM_node[0].pos=0;
}

void SAM_add(int x,int len)
{
    SAM_Node *p=SAM_last,*np=newSAM_Node(p->len+1);
    np->pos=len; SAM_last=np;
    for(;p&&!p->next[x];p=p->fa) p->next[x]=np;
    if(!p)
    {
        np->fa=SAM_root; return ;
    }
    SAM_Node *q=p->next[x];
    if(p->len+1==q->len)
    {
        np->fa=q; return;
    }
    SAM_Node *nq=newSAM_Node(q);
    nq->len=p->len+1;
    q->fa=nq; np->fa=nq;
    for(;p&&p->next[x]==q;p=p->fa)
        p->next[x]=nq;
}

void SAM_build(char * s)
{
    SAM_init();
    int len=strlen(s);
    for(int i=0;i<len;i++)
        SAM_add(s[i]-'a',i+1);
}

char str[maxn];
int the_last=-1;

void dfs(SAM_Node* head,int n)
{
    if(n==0)
    {
        the_last=head->pos;
        return ;
    }
    for(int i=0;i<26;i++)
    {
        if(head->next[i])
        {
            dfs(head->next[i],n-1);
            return ;
        }
    }
}

int main()
{
    int T_T;
    scanf("%d",&T_T);
    while(T_T--)
    {
        scanf("%s",str);
        int n=strlen(str);
        for(int i=0;i<n;i++)
            str[i+n]=str[i];
        str[2*n]=0;
        SAM_build(str);
        SAM_Node *temp=SAM_root;
        n=strlen(str);
        dfs(temp,n/2);
        printf("%d\n",the_last+1-n/2);
    }
    return 0;
}

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/118888.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 记 – PC视频播放最强画质教程(Potplayer + madVR)「建议收藏」

    记 – PC视频播放最强画质教程(Potplayer + madVR)「建议收藏」PC视频播放最强画质教程前言:本次使用到的软件/工具Potplayer播放器Potplayer是目前我用到的最好用的宝藏视频播放软件:内存占用低、无广告、支持视频格式多、功能强大、扩展性高、界面唯美(网上下载皮肤)。MADVR插件MADVR是一款超强的视频插件,其配合高清播放软件,可以做到目前PC上播放高清视频的最强画质。MADVR这款视频渲染器比市面上大多数播放器自带的渲染器有着更精确的颜色处理,更高质量的图像缩放缩放、以及更低的颜色错误率。这就使得它所渲染出来的视频在

  • 2021.9 idea MyBatis Log Plugin 激活码(JetBrains全家桶)

    (2021.9 idea MyBatis Log Plugin 激活码)本文适用于JetBrains家族所有ide,包括IntelliJidea,phpstorm,webstorm,pycharm,datagrip等。IntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,下面是详细链接哦~https://javaforall.cn/100143.html…

  • Elasticsearch日期格式化「建议收藏」

    Elasticsearch日期格式化「建议收藏」参照以下文章进行日期格式化即可,传送门:https://blog.csdn.net/smilepasta035/article/details/79550400

  • 【动态规划】01背包问题(通俗易懂,超基础讲解)[通俗易懂]

    【动态规划】01背包问题(通俗易懂,超基础讲解)[通俗易懂]问题描述有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和?为方便讲解和理解,下面讲述的例子均先用具体的数字代入,即:eg:number=4,capacity=8i(物品编号) 1 2 3 4 w(体积) 2 3 4 5 v(价值) 3 4 5 6 总…

  • jsp printwriter_java socket编程

    jsp printwriter_java socket编程JavaPrintWriter类在本教程中,我们将通过示例来学习JavaPrintWriter及其print()和printf()方法。java.io包的PrintWriter类可用于以通常可读的形式(文本)写入输出数据。它继承了抽象类Writer。PrintWriter的工作方式与其他写入器不同,PrintWriter将原始数据(int、float、char等)转换为文本格式。然后它将格式…

  • SpringBoot面试题大汇总附答案,SpringBoot面试题-持续更新中「建议收藏」

    SpringBoot面试题大汇总附答案,SpringBoot面试题-持续更新中「建议收藏」2021最新SpringBoot面试题【附答案解析】SpringBoot面试题及答案2021,SpringBoot2021最新面试题及答案,SpringBoot面试题新答案已经全部更新完了,有些答案是自己总结的,也有些答案是在网上搜集整理的。这些答案难免会存在一些错误,仅供大家参考。如果发现错误还望大家多多包涵,不吝赐教,谢谢~SpringBoot最新面试题大汇总,附答案其实,博主还整理了,更多大厂面试题,直接下载吧下载链接:高清172份,累计7701页大厂面试题PDF1、SpringBoo

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号