目錄DescriptionInputOutputSample InputSample Output題解

Description

給定兩個項鏈的表示，判斷他們是否可能是一條項鏈。

Input

輸入文件只有兩行，每行一個由0至9組成的字符串，描述一個項鏈的表示（保證項鏈的長度是相等的）。

Output

如果兩條項鏈不可能同構，那么輸出’No’，否則的話，第一行輸出一個’Yes’

第二行輸出該項鏈的字典序最小的表示。 設L = 項鏈長度，L <= 1000000。

Sample Input

2234342423
2423223434

Sample Output

Yes
2234342423

題解

最小表示法

#include<iostream>
#include<cstdio>
using namespace std;

const int L=2002002;
int l,s1[L],s2[L],k1,k2;

void Scanf(int s[L])
{
	l=0; char c=getchar();
	while(c<'0'||c>'9') c=getchar();
	for(;c>='0'&&c<='9';) s[l++]=(c^48),c=getchar();
	for(int i=0;i<l;++i) s[i+l]=s[i];
}

int MinAns(int s[L])
{
	int i=0,j=1,k;
	for(;i<l&&j<l;)
	{
		k=0;
		for(;s[i+k]==s[j+k];) ++k;
		if(k==l) break;
		if(s[i+k]<s[j+k]) j+=k+1;
		else i+=k+1;
		if(i==j) ++j;
	}
	return min(i,j);
}

int Check()
{
	for(int i=k1,j=k2,k=0;k<l;++k)
		if(s1[i+k]!=s2[j+k]) return 0;
	return 1;
}

int main()
{
	Scanf(s1),Scanf(s2);
	k1=MinAns(s1),k2=MinAns(s2);
	if(Check())
	{
		puts("Yes");
		for(int i=0;i<l;++i) printf("%d",s1[i+k1]);
	}
	else puts("No");
	return 0;
}

總結

以上是生活随笔為你收集整理的[bzoj1398] 寻找主人的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。