[BZOJ4974][Lydsy1708月赛]字符串大师(KMP)

发布于 2018-03-24  84 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4974][Lydsy1708月赛]字符串大师(KMP)

Description

一个串T是S的循环节,当且仅当存在正整数k,使得S是T^k(即T重复k次)的前缀,比如abcd是abcdabcdab的循环节。给定一个长度为n的仅由小写字符构成的字符串S,请对于每个k(1<=k<=n),求出S长度为k的前缀的最短循环节的长度per_i。字符串大师小Q觉得这个问题过于简单,于是花了一分钟将其AC了,他想检验你是否也是字符串大师。
小Q告诉你n以及per_1,per_2,...,per_n,请找到一个长度为n的小写字符串S,使得S能对应上per。

Tag

KMP

解决思路

把我们之前从 Next 推循环节长度的方式反过来。现在给出每一个前缀的最短循环节长度,就相当于给出了 Next。
接下来考虑用 Next 反构造出字典序最小的原串。
其实与构造 Next 的过程很像。向前走到第一个 j+1==Next[i] 的位置,然后就可以知道 str[i] 要与 str[j+1 ]相同。是不是与在构造 KMP 中要求str[j+1]==str[i] 类似?
当然要注意,可能会一直走都头都没有合法位置,那么此时就要找到第一个能够放的字符(字典序最小),为了找到这个字符,需要在跳 Next 的时候在不匹配的时候要标记这个位置不能放的字符。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=100010;
const int maxAlpha=26;
const int inf=2147483647;

int n;
int Next[maxN];
bool Alpha[maxAlpha][maxN];
char str[maxN];

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        int len;
        scanf("%d",&len);//读入循环节,同时构造出Nexr数组
        Next[i]=i-len;
    }
    Next[0]=-1;//根据Next数组反推出原字符串的关系
    for (int i=1;i<=n;i++)
    {
        int j=Next[i-1];
        while ((j!=-1)&&(Next[i]!=j+1))//失配,则继续向前跳Next,同时记录这个位置上不能放的字符
        {
            Alpha[str[j+1]-'a'][i]=1;
            j=Next[j];
        }
        if (j!=-1) str[i]=str[j+1];//若最终找到了,则与找到的位置匹配
        else
            for (int pos=0;pos<maxAlpha;pos++)//否则,填上最小的在之前的失配过程中没有被标记为不能放的最小字符
                if (Alpha[pos][i]==0)
                {
                    str[i]=pos+'a';
                    break;
                }
    }
    for (int i=1;i<=n;i++) printf("%c",str[i]);
    return 0;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ4974][Lydsy1708月赛]字符串大师(KMP)


HNCJ OIer