vijos1382寻找主人

题目大意：

给出两个串（长度<=1e6），问是否同构，如果同构输出最小表示。

题解：

这是最小表示法模板题。在这里好好讲一下最小表示法。

首先有一个最暴力的方法：
把所有表示搞出来排序。

时间复杂度O(n^2logn);

然后可以发现，比较两个字符串时都是从第一位向后比。

伪代码：

char s[N<<];

int mex()

{

    scanf("%s",s+);

    int len = strlen(s+);

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

        s[i+len]=s[i];

    int i=,j=,k=;

    while(i<=len&&j<=len&&k<len)

    {

        int t = s[i+k]-s[j+k];

        if(!t)k++;

        else

        {

            if(t>)i++;

            else j++;

            k=;

            if(i==j)i++;

        }

    }

    return i<j?i:j;

}

时间复杂度O(n^2);

看起来可以再优化一下。

比如当前串是

S1S2S3S4S5S6S7S8

指针i,j分别走到S1和S5。

k=2。

这时S1S2和S5S6相同。

然后比较S3和S7。假设S3>S7，那么i直接跳过S3到达S4。

因为如果要作开头的话，S1不如S5，S2不如S6，S3不如S7;

公共原因：S3<S7。

因此模板：

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 1000050

char a[][*N];

int len;

int mex(int t)

{

    int i=,j=,k=;

    while(i<=len&&j<=len&&k<len)

    {

        int tmp = a[t][i+k]-a[t][j+k];

        if(!tmp)k++;

        else

        {

            if(tmp>)i+=k+;

            else j+=k+;

            if(i==j)j++;

            k=;

        }

    }

    return i<j?i:j;

}

int main()

{

    scanf("%s%s",a[]+,a[]+);

    len = strlen(a[]+);

    for(int i=;i<=len;i++)a[][len+i]=a[][i],a[][len+i]=a[][i];

    int l1 = mex(),l2 = mex();

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

        if(a[][l1+i]!=a[][l2+i])

        {

            printf("No\n");

            return ;

        }

    printf("Yes\n");

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

        printf("%c",a[][l1+i]);

    printf("\n");

    return ;

}