洛谷P1709 [USACO5.5]隐藏口令Hidden Password(…

2018-06-29 06:14:44来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

题目描述

有时候程序员有很奇怪的方法来隐藏他们的口令。Binny会选择一个字符串S(由N个小写字母组成,5<=N<=5,000,000),然后他把S顺时针绕成一个圈,每次取一个做开头字母并顺时针依次取字母而组成一个字符串。这样将得到一些字符串,他把它们排序后取出第一个字符串。把这个字符串的第一个字母在原字符串中的位置-1做为口令。

如字符串alabala,按操作的到7个字符串,排序后得:

aalabal

abalaal

alaalab

alabala

balaala

laalaba

labalaa

第一个字符串为aalabal,这个a在原字符串位置为7,7-1=6,则6为口令。

输入输出格式

输入格式:

 

第一行:一个数:N

第二行开始:字符串:S(每72个字符一个换行符)

 

输出格式:

 

一行,为得到的口令

 

输入输出样例

输入样例#1: 复制
7
anabana
输出样例#1: 复制
6

说明

题目满足:

30%的数据n<=10000

70%的数据n<=100000

100%的数据n<=5000000

时限 1s

题目翻译来自NOCOW。

USACO Training Section 5.5

//20170523新增数据四组

 

这次后缀自动机卡不过去了qwq。尼玛空间太小了。。

然后就只能用最小表示法的专用算法了。大致流程就是维护三个指针$i, j, k$,然后判断$s[i+k]$和$s[j+k]$这两个位置哪个小,贪心的选

// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 5000001;
int N;
char s[MAXN];
int fa[MAXN], len[MAXN], ch[MAXN][26], tot = 1, last = 1, root = 1; 
void insert(int x) {
    int now = ++tot, pre = last; last = now; len[now] = len[pre] + 1;
    for(; pre && !ch[pre][x]; pre = fa[pre]) 
        ch[pre][x] = now;
    if(!pre) fa[now] = root;
    else {
        int q = ch[pre][x];
        if(len[q] == len[pre] + 1) fa[now] = q;
        else {
            int nows = ++tot; len[nows] = len[pre] + 1;
            memcpy(ch[nows], ch[q], sizeof(ch[q]));
            fa[nows] = fa[q]; fa[q] = fa[now] = nows;
            for(; pre && ch[pre][x] == q; pre = fa[pre]) ch[pre][x] = nows;
        }
    }
}
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    scanf("%d\n", &N);
    for(int i = 1; i <= N; i++) {
        s[i] = getchar();
        if(i % 72 == 0) getchar(), getchar();
    }
    tot = last = root = 1;
    for(int i = 1; i <= N; i++) s[i + N] = s[i];
    N <<= 1;
    for(int i = 1; i <= N; i++) insert(s[i] - 'a');
    int now = root, tot = 0;
    for(; tot <= N / 2; tot++) {
        for(int i = 0; i <= 25; i++) 
            if(ch[now][i])
                {now = ch[now][i];  break;}    
    } 
    printf("%d\n", len[now] - N / 2 - 1);
    return 0;
}
后缀自动机85
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXN = 5000001;
int N;
char s[MAXN]; 
int main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin >> N;
    for(int i = 0; i < N; i++) cin >> s[i];
    int i = 0, j = 1, k = 0;
    while(i < N && j < N) {
        k = 0;
        while(s[(i + k) % N] == s[(j + k) % N] && k < N) k++;
        if(k == N) return !printf("%d", min(i, j));
        if(s[(i + k) % N] > s[(j + k) % N]) i = i + k + 1;
        else j = j + k + 1;
        if(i == j) j++;
    }
    printf("%d", min(i, j));
    return 0;
}

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:大专生自学c++到找到工作的前前后后

下一篇:Floyd 算法详解