用最小表示法做的
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1e6+5;

char a[maxn], b[maxn];

int calc(char *s)
{
int n=strlen(s+1);
for(int i=1;i<=n;i++) s[n+i]=s[i];
int i=1, j=2, k;
while(i<=n && j<=n)
{
for(k=0; k<=n && s[i+k]==s[j+k]; k++);
if(k==n) break;
if(s[i+k]>s[j+k])
{
i=i+k+1;
if(i==j) i++;
}
else
{
j=j+k+1;
if(i==j) j++;
}
}
return min(i, j);
}

int main()
{
scanf("%s", a+1);
scanf("%s", b+1);
int l1=strlen(a+1), temp1=calc(a);
int l2=strlen(b+1), temp2=calc(b);
a[l1+temp1]=b[l2+temp2]=0;
if(l1==l2 && !strcmp(a+temp1, b+temp2))
{
printf("Yes\n");
printf("%s", a+temp1);
}
else printf("No\n");
return 0;
}

后缀自动机
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 10000009;
const int cn = 10;

struct Node {
Node *fa, *ch[cn];
int len;
} pool[maxn], *pt, *root, *last;

Node* newNode(int v) {
pt->fa = NULL;
pt->len = v;
memset(pt->ch, 0, sizeof pt->ch);
return pt++;
}

void init() {
pt = pool;
last = root = newNode(0);
}

void Extend(int c) {
Node* p = last, np = newNode(p->len + 1);
for(; p && !p->ch[c]; p = p->fa)
p->ch[c] = np;
if(!p)
np->fa = root;
else {
Node q = p->ch[c];
if(p->len + 1 == q->len)
np->fa = q;
else {
Node* nq = newNode(p->len + 1);
memcpy(nq->ch, q->ch, sizeof nq->ch);
nq->fa = q->fa;
q->fa = np->fa = nq;
for(; p && p->ch[c] == q; p = p->fa)
p->ch[c] = nq;
}
}
last = np;
}

void Get(char s[], int len) {
Node* p = root;
for(int lth = 0; lth < len; lth++)
for(int i = 0; i < cn; i++) if(p->ch[i]) {
p = p->ch[i];
s[lth] = i + '0';
break;
}
}

char str[maxn], s[maxn];
int N;

bool solve() {
Node* p = root;
for(int lth = 0; lth < N; lth++)
for(int i = 0; i < cn; i++) if(p->ch[i]) {
if(i != str[lth] - '0')
return false;
p = p->ch[i];
break;
}
return true;
}

int main() {

scanf("%s", str);
N = strlen(str);

init();
for(int i = 0; i < 2; i++)
for(int j = 0; j < N; j++)
Extend(str[j] - '0');

Get(str, N);
str[N] = '\0';

scanf("%s", s);

init();
for(int i = 0; i < 2; i++)
for(int j = 0; j < N; j++)
Extend(s[j] - '0');

if(solve())
printf("Yes\n%s\n", str);
else
puts("No");

return 0;
}

KMP

。。。郁闷。每次弄这种题目都遇到灵异事件。。

交上去。Conan。。AC。突然变成Roo。。结果显示AC.状态那里

Tle..

找到两串字典序最小的比较下

至于怎么找字典序最小有个跳跃性的方法，

楼上应该有讲吧

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

呜呜用数组的话最后要WRITELN的！！！

可以直接用最小表示法求出两个串的最小表示

判断它是否相同

就不用KMP了

orz Vijos Dragon……

Victoria Roo中毒了？……

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时|格式错误...

├ 测试数据 07：运行超时|格式错误...

├ 测试数据 08：运行超时|格式错误...

├ 测试数据 09：运行超时|格式错误...

├ 测试数据 10：答案正确... 0ms

为什么~~~~~~~~~~~交了N遍

KMP 蛮好的

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

找最小输出位置可以这样：

procedure findmin;

begin

min:=1;k:=0;

for i:=2 to length(s3)do

if s3[min+k]>s3[i]then begin min:=i-k;k:=0;end

else if s3[min+k]=s3[i] then inc(k)

else k:=0;

end;

中间几个测试数据怎么回事，我得到的是‘Yes’，他是‘No’，我改成‘No’，他又来‘Yes’。RP问题

为什么 分别求 最小 表示 后 再 比较 是否 一样 会出现：

├ 测试数据 07：运行超时...

Unaccepted 有效得分：90 有效耗时：0ms

第七组 有什么 特别 神奇 的地方吗 ……

更 神奇 的 ， 我 又 交 一遍 ，还是没有100分 ， 但是 却 AC 了 ……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 41ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

自己机子上1000000的数据必定超时,莫非VIJOS有世界顶尖的超级计算机,每秒运算可以突破1亿亿次.

可以倍增+KMP

但是我还是用最小表示法了，详见zy的论文，有详细的证明。

原本可以两个串来做直接判断同构，但还要打字典序最小的，所以还是要分别做两次。

p.s 6k shit!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

第100个,Puppy无敌

几个月前,我用了最小表示法,结果潮湿,后我又用更加快的最小表示法还是潮湿,

今天我把第一个程序提交 ac!!!

同一个程序，什么都没改，一次90（超一个)，一次ac(全0ms）。。。。无语...

先判断是否同构，在求一个串的最小表示。。

核心：

i:=1;

j:=2;

k:=0;

while (i

这题要靠puppy啊，6k直接挂。

先来个把第一个串重复两遍，然后kmp匹配一下，如果成功则再用最小表示法。

注意：不要用mod运算，要用减法。

最小表示法.

我是看这个学的:

http://hi.baidu.com/js_zheng/blog/item/fdb45d09977ddec93bc763b5.html

我居然把这道题A了……本来说联系最小表示法，做了这道题……结果把最小表示法忘了……囧，当即复习，会了，想交题的时候发现自己A了……看来我的记忆力……

果然

puppy真是伟大