HDU - 3746(next数组的应用)

刷都可以刷

HDU - 3746

题意：

现在你有一个长为$n$的字符串（只包含小写字母），现在你要在他左边或者右边加最少的字符，使这个串变成一个周期大于$1$的周期串。

题解：

不难发现，在右边添加是最优的，在左边可能会破坏原有的周期，然后我们看一下，就可以发现，我们要的是这个字符串最后的$next$值，最后看看$len-next[len]$与$len$的关系即可。

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define endl '\n'


const int N=1e5+5;
int nx[N];
void gn(string s){
  int i=0,j=-1;
  nx[0]=-1;
  while(i<s.size()){
    if(j==-1||s[i]==s[j])++i,++j,nx[i]=j;
    else j=nx[j];
  }
}
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    string s;cin>>s;
    int n=s.size();
    gn(s);
    int m=n-nx[n];
    if(m==n)cout<<m<<endl;
    else if(n%m)cout<<m-n%m<<endl;
    else cout<<"0\n";
  }
  return 0;
}

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/11/13/HDU-3746-next数组的应用/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！