[Acwing158]项链(字符串)

https://www.acwing.com/problem/content/description/160/

看leetcode昨天的难题的题解 y总随口提了一下最小表示法 于是乎就有了这篇题解

求一个字符串的最小表示 即将字符串置换 求哪种置换时 得到的字符串字典序最小 求这一最小表示

如32245781 最小表示为13224578

具体求法 首先将字符串复制到最后 以解决字符串成环问题

之后用双指针i=0 j=1

如果s[i]==s[j] 则将i j均后移 直到 s[i]!=s[j]

假设s[i]>s[j]表面从j开始的字符串要优于从i开始的 则舍弃i 同时舍弃i+1、i+2一直到不相等的位置

更新i=k+1 因此O(n)时间复杂度即可求出答案

详情见代码 讲的有点乱 因此这题求一下两个字符串的最小表示 同时比较这两个最小表示是否相等即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 10;

int n;
string a, b;

int get_min(string t)
{
  int i = 0, j = 1;
  while (i <= n && j <= n)
  {
    int k = 0;
    while (k < n && t[i + k] == t[j + k])
    {
      //当前位相等
      k++;
    }
    if (k == n)
    {
      //到最后一直都相等 说明字符串是由同一字母构成的
      break;
    }
    if (t[i + k] > t[j + k])
    {
      // i指向的字符串大 舍弃i
      i += k + 1;
    }
    else
    {
      j += k + 1;
    }
    if (i == j)
      i++; // j++
  }
  int res = min(i, j); //一定有一个跑出界了
  return res;
}

int main()
{
  cin >> a >> b;
  n = a.length();
  a = a + a;
  b = b + b;
  int ap = get_min(a), bp = get_min(b);
  string na = a.substr(ap) + a.substr(0, ap - 1);
  string nb = b.substr(bp) + b.substr(0, bp - 1);
  if (na == nb)
  {
    cout << "Yes" << endl;
    cout << na << endl;
  }
  else
  {
    cout << "No" << endl;
  }
  return 0;
}