CH1807 Necklace【Hash】【字符串】【最小表示法】

1807 Necklace 0x18「基本数据结构」练习

背景

有一天，袁☆同学绵了一条价值连城宝石项链，但是，一个严重的问题是，他竟然忘记了项链的主人是谁！在得知此事后，很多人向☆同学发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。 ☆同学要求每个人都写了一段关于自己项链的描述：项链上的宝石用数字0至9来标示。一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如如下项链： 1-2-3-4 它的可能的四种表示是0123、1230、2301、3012。袁☆同学现在心急如焚，于是他找到了你，希望你能够编一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。。

描述

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

输入格式

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

输出格式

如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。

样例输入

2234342423

2423223434

样例输出

Yes

2234342423

数据范围与约定

设L = 项链长度，对于50%的数据L <= 100000；对于100%的数据L <= 1000000。

题意：

给两个字符串，问他们是不是同构的。如果是，输出他的最小表示。

思路：

首先求出第一个字符串的Hash值，然后在第二个字符串后面接一倍。枚举第二个字符串起始点，求Hash值与第一个的比较，如果找到了匹配的说明是同构的。

找到同构的之后就找第二个字符串的最小表示。每次枚举两个串的起始，找到他们不相同的开始位置，进行比较，保留较小的。

 #include <iostream>

 #include <set>

 #include <cmath>

 #include <stdio.h>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <map>

 using namespace std;

 typedef long long LL;

 #define inf 0x7f7f7f7f

 const int maxn = 1e6 + ;

 char str1[maxn], str2[maxn * ];

 unsigned long long H1, p[maxn * ], H2[maxn * ];

 int main()

 {

     scanf("%s", str1 + );

     int len = strlen(str1 + );

     p[] = ;

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

         p[i] = p[i - ] * ;

         H1 = H1 *  + str1[i] - '';

     }

     scanf("%s", str2 + );

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

         str2[i] = str2[i - len];

     }

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

         H2[i] = H2[i - ] *  + str2[i] - '';

     }

     bool flag = false;

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

         if(H2[i + len] - H2[i] * p[len] == H1){

             flag = true;

             printf("Yes\n");

         }

     }

     if(flag){

         int i = , j = , k;

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

             for(k = ; k <= len && str2[i + k] == str2[j + k]; k++);

             if(k == len)break;

             if(str2[i + k] > str2[j + k]){

                 i = i + k + ;

                 if(i == j)i++;

             }

             else{

                 j = j + k + ;

                 if(i == j)j++;

             }

         }

         int ans = min(i, j);

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

             printf("%c", str2[ans + i]);

         }

         printf("\n");

     }

     else{

         printf("No\n");

     }

     return ;

 }

巴特西