[bzoj 1398] Vijos1382寻找主人 Necklace 解题报告（最小表示法）

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1398

题目：

Description

给定两个项链的表示，判断他们是否可能是一条项链。

Input

输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。

Output

如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’

第二行输出该项链的字典序最小的表示。设L = 项链长度，L <= 1000000。

Sample Input

2234342423
2423223434

Sample Output

Yes
2234342423

题解：

很显然我们只需要分别求出两个字符串的最小表示法，然后对比一下是否相同就好了

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cstdio>

using namespace std;

const int N=1e6+;

int n;

int exp(char ch[])

{

    int i=,j=,k;

    while (i<=n&&j<=n)

    {

        for (k=;k<=n&&ch[i+k]==ch[j+k];k++);

        if (k==n) break;

        if (ch[i+k]>ch[j+k])

        {

            i=i+k+;

            if (i==j) i++;

        }

        else

        {

            j=j+k+;

            if (i==j) j++;

        }

    }

    return min(i,j);

}

int main()

{

    char ch1[N],ch2[N];

    scanf("%s",ch1+);

    scanf("%s",ch2+);

    n=strlen(ch1+);

    for (int i=;i<=n;i++) ch1[i+n]=ch1[i];

    for (int i=;i<=n;i++) ch2[i+n]=ch2[i];

    int x=exp(ch1);

    int y=exp(ch2);

    bool flag=true;

    for (int i=;i<n;i++)

    {

        if (ch1[x+i]!=ch2[y+i])

        {

            flag=false;

            break;

        }

    }

    if (!flag)

    {

        puts("No");

        return ;

    }

    puts("Yes");

    for (int i=;i<n;i++)

    {

        printf("%c",ch1[x+i]);

    }

    return ;

}

巴特西