题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4516
考试的时候,一看到要动态维护就把SA扔一边凉快去了QAQ
想一想,不能这么草率啊!
来说一说SA和SAM两种做法
1) SAM:
很明显就是求一个字符串本质不同的字串个数
SAM本身就是增量构造,于是就成裸题了
2) SA:
考虑离线之后,先逆序建一个完整的出来
那么加入一个字符,实际上就是加入了一个后缀
那么其对于答案的贡献,就是原来的height数组搞一搞
实现的话,搞一个RMQ什么的就好
代码的话,我们来召唤Menci:https://oi.men.ci/sdoi2016-incantation/
自己太懒,于是就只写了SAM的代码:
#include<bits/stdc++.h> #include<tr1/unordered_map> #define LL long long using namespace std; using namespace tr1; const int N = 200000+9; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } namespace Suffix_Automaton{ #define SAM Suffix_Automaton int len[N],fail[N],cnt,tail; unordered_map<int,int> ch[N]; inline int Extend(int c) { int w = tail; tail = ++cnt; len[tail] = len[w] + 1; while (w&&!ch[w]) ch[w] = cnt, w = fail[w]; if (!w) fail[tail] = 1; else { if (len[ch[w]] == len[w]+1) fail[tail] = ch[w]; else { int to = ch[w]; ch[++cnt] = ch[to]; fail[cnt] = fail[to]; fail[to] = cnt; fail[tail] = cnt; len[cnt] = len[w] + 1; while (ch[w] == to) ch[w] = cnt, w = fail[w]; } } return len[tail] - len[fail[tail]]; } inline void solve(int n) { cnt = tail = 1; for (LL i=1,vout=0;i<=n;i++) printf("%lld\n",vout+=Extend(read())); } }; int main(){ SAM::solve(read()); return 0; }
—– UPD 2016.9.29 —–
这™map比unordered_map快这么多有几个意思QAQ
这种感觉……
真·生无可恋
I have not checked in here for a while because I thought it was getting boring, but the last several posts are great quality so I guess I’ll add you back to my daily bloglist. You deserve it my friend 🙂
I’ve been absent for a while, but now I remember why I used to love this blog. Thanks , I’ll try and check back more often. How frequently you update your site?