---
title: "项链"
created: 2025-11-28
tags:
  - 算法
---

# 项链

## 题目 [项链](https://www.acwing.com/problem/content/description/160/)

![[image-6a42c933.png]]

## 思路分析

检查是否为子串很容易

直接复制一份在后面当做循环

然后在这个长的里面find短的

主要是最小表示法的实现

尝试用char[]做一遍 但是因为涉及很多拷贝操作 只能过7个数据 会tle

但后面其实发现这个问题问的其实是两个字符串的最小表示法是否相等

（一开始写的时候不知道什么是最小表示法 所以把判断逻辑先写了 然后才补的最小表示法输出）

## 代码实现

**315ms**

```cpp
#include<bits/stdc++.h>

using namespace std;

string a,b,c;

int getMinRepresentation(string s) {

    s += s;

    int len = s.length() / 2, i = 0, j = 1, k;

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

        k = 0;

        while(k < len && s[i+k] == s[j+k])

            k++;

        if(k == len)

            break;

        if(s[i+k] > s[j+k])

            i += k + 1;

        else

            j += k + 1;

        if(i == j)

            j++;

    }

    return min(i, j);

}

int main()

{

    cin>>a;

    c=a+a;

    cin>>b;

    if(c.find(b)==-1)

        cout<<"No"<<endl;

    else{

        cout<<"Yes"<<endl;

        int pos = getMinRepresentation(a);

        for(int i = pos; i < pos + a.length(); i++) {

            cout << a[i % a.length()];

        }

        cout << endl;

    }

    return 0;

}
```

**tle**

```cpp
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2000010;

char a[MAXN], b[MAXN], temp[2 * MAXN];

int getMinRepresentation(char s[], int len) {

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

        temp[i] = s[i];

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

    }

    temp[2 * len] = '\0';

    int i = 0, j = 1, k;

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

        k = 0;

        while (k < len && temp[i + k] == temp[j + k])

            k++;

        if (k == len)

            break;

        if (temp[i + k] > temp[j + k])

            i += k + 1;

        else

            j += k + 1;

        if (i == j)

            j++;

    }

    return min(i, j);

}

int main() {

    scanf("%s", a);

    scanf("%s", b);

    string c = a; c += c;

    if(c.find(b) == string::npos)

        printf("No\n");

    else {

        printf("Yes\n");

        int pos = getMinRepresentation(a, strlen(a));

        for (int i = pos; i < pos + strlen(a); i++) {

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

        }

        printf("\n");

    }

    return 0;

}
```

**94ms**

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=2000010;

char a[N],b[N];

int n;

int get_min(char s[]){

    int i=0,j=1,k;

    while(i<=n && j<=n)

    {

        k=0;

        while(k<n && s[i+k]==s[j+k])

            k++;

        if(k==n)

            break;

        if(s[i+k]>s[j+k])

            i+=k+1;

        else

            j+=k+1;

        if(i==j)

            j++;

    }

    int res=min(i,j);

    s[res+n]='\0';

    return res;

}

int main()

{

    scanf("%s%s",a,b);

    n=strlen(a);

    memcpy(a+n,a,n);

    memcpy(b+n,b,n);

    int ap=get_min(a),bp=get_min(b);

    if(strcmp(a+ap,b+bp))

        puts("No");

    else

    {

        puts("Yes");

        puts(a+ap);

    }

    return 0;

}
```

**309ms**

```cpp
#include<bits/stdc++.h>

using namespace std;

string a,b;

int n;

string get_min(string s){

    int i=0,j=1,k;

    while(i<=n && j<=n)

    {

        k=0;

        while(k<n && s[i+k]==s[j+k])

            k++;

        if(k==n)

            break;

        if(s[i+k]>s[j+k])

            i+=k+1;

        else

            j+=k+1;

        if(i==j)

            j++;

    }

    int res=min(i,j);

    string ans=s.substr(res,n);

    return ans;

}

int main()

{

    cin>>a>>b;

    n=a.size();

    a+=a;

    b+=b;

    string ap=get_min(a),bp=get_min(b);

    if(ap!=bp)

        puts("No");

    else

    {

        puts("Yes");

        cout<<ap;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[雪花雪花雪花|雪花雪花雪花]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/离散化相关问题/区间和|区间和]]