1398: Vijos1382寻找主人 Necklace

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 308  Solved: 129

Description

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

Input

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

Output

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

Sample Input

2234342423
2423223434

Sample Output

Yes
2234342423

HINT

Source

【分析】

  最小表示法。。有点忘了。。

 #include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1000010 char s1[*Maxn],s2[*Maxn];
int l; int mymin(int x,int y) {return x<y?x:y;} int ffind(char *s)
{
int i=,j=,k=;
while(i+k<=l&&j+k<=l)
{
if(s[i+k]==s[j+k]) k++;
else if(s[i+k]<s[j+k]) j+=k+,k=;
else i+=k+,k=;
if(i==j) j++;
}
return mymin(i,j);
} int main()
{
scanf("%s%s",s1,s2);
l=strlen(s1);
for(int i=;i<l;i++) s1[i+l]=s1[i];
for(int i=;i<l;i++) s2[i+l]=s2[i];
int a=ffind(s1),b=ffind(s2);
bool ok=;
for(int i=;i<l;i++) if(s1[a+i]!=s2[b+i]) {ok=;break;}
if(!ok) printf("No\n");
else
{
printf("Yes\n");
for(int i=;i<l;i++) printf("%c",s1[a+i]);
printf("\n");
}
return ;
}

2017-04-17 08:14:10

最新文章

  1. Response.End()出现ThreadAbortException 异常
  2. Android中图像变换Matrix的原理、代码验证和应用(三)
  3. hdu 4411 arrest 最小费用流
  4. C编程风格.
  5. 复习C语言系列二:动态调用函数指针数组
  6. Android(Lollipop/5.0) Material Design(六) 使用图像
  7. PHP中require()文件包含的正确用法
  8. s​q​l​ ​s​e​r​v​e​r​ ​2​0​0​0​登​录​名​与​数​据​库​用​户​名​的​关​联​问​题
  9. BeanUtils制作自定义的转换器
  10. dubbo服务暴露
  11. nginx 动态添加ssl模块
  12. vue项目实战中的增、删、改、查
  13. (PMP)第12章-----项目采购管理
  14. Dart语言快速学习上手(新手上路)
  15. 排座椅(洛谷P1056)
  16. servlet保存数据的几种方式
  17. The serializable class XXX does not declare a static final serialVersionUID field of type long
  18. Mybatis初始
  19. C#多个线程同时执行一个任务示例
  20. 用国内镜像源pip加速安装模块

热门文章

  1. 对 JavaScript 进行单元测试的工具
  2. JavaScript数据类型和转换
  3. js刷题:leecode 25
  4. Chrome浏览器任意修改网页内容
  5. escapeRegExp捕捉通配符的代码解析
  6. 用js拼接url为pathinfo模式
  7. Java的继承和多态
  8. 服务器部署之nginx的配置
  9. xargs -i 和-I 的区别【转】
  10. centos如何设置定时任务