湘潭网站建设 要上磐石网络,学编程用什么笔记本电脑比较好,惠州的企业网站建设,网站网络设计是怎么做的传送门
题意#xff1a;
求sss的最小表示。 ∣s∣≤1e4|s|\le 1e4∣s∣≤1e4
思路#xff1a;
可以选择直接套最小表示法的板子#xff0c;但也可以将sss复制#xff0c;即ssssssssssss#xff0c;对ssssss建samsamsam#xff0c;让后贪心的找一个长度为nnn的字典序最…传送门
题意
求sss的最小表示。
∣s∣≤1e4|s|\le 1e4∣s∣≤1e4
思路
可以选择直接套最小表示法的板子但也可以将sss复制即ssssssssssss对ssssss建samsamsam让后贪心的找一个长度为nnn的字典序最小的子串这个可以直接遍历得到让后其len−n1len-n1len−n1即为答案。
// Problem: Glass Beads
// Contest: Virtual Judge - UVA
// URL: https://vjudge.net/problem/UVA-719
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n;
int last1,tot1,len;
int ed[N];
char s[N];
struct Node {int ch[26];int len,fa;
}sam[N*2];void init() {for(int i1;itot;i) {for(int j0;j26;j) sam[i].ch[j]0;sam[i].lensam[i].fa0;}lasttot1; len0;
}void add(int c,int id) {int plast,nplasttot; sam[np].lensam[p].len1;while(p!sam[p].ch[c]) {sam[p].ch[c]np;psam[p].fa;} if(!p) sam[np].fa1;else {int qsam[p].ch[c];if(sam[q].lensam[p].len1) sam[np].faq;else {int nqtot; sam[nq]sam[q];sam[nq].lensam[p].len1;sam[q].fasam[np].fanq;while(psam[p].ch[c]q) {sam[p].ch[c]nq;psam[p].fa;}}}
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);int _; scanf(%d,_);while(_--) {init();scanf(%s,s1); nstrlen(s1);for(int i1;in;i) add(s[i]-a,i);for(int i1;in;i) add(s[i]-a,i);int st1,nnn;stsam[st].ch[m-a];stsam[st].ch[a-a];printf(%d\n,sam[st].len);}return 0;
}
/**/
