做网站需要专业,移动端优质网页,经典软文案例50字,一个专门做视频配音的网站P4070 [SDOI2016]生成魔咒
题意#xff1a;
有n个字符xi#xff0c;每次在S的末尾加入一个字符#xff0c;(一开始S为空)#xff0c;每次加入xi后的不相同字串有多少个
题解#xff1a;
做这个题首先要会后缀数组P3809 【模板】后缀排序#xff0c;还要知道不同的子串…P4070 [SDOI2016]生成魔咒
题意
有n个字符xi每次在S的末尾加入一个字符(一开始S为空)每次加入xi后的不相同字串有多少个
题解
做这个题首先要会后缀数组P3809 【模板】后缀排序还要知道不同的子串如何求P2408 不同子串个数这两个题我都有写过博客 对于一个字符串我们在其末尾加一个新字符对这个字符串的height等变换还是很大的整个格局都会被打乱(因为我们是后缀数组在最后加所有后缀都会改变)。但是如果我们在前面加在最前面加字符那只会额外产生一个新字符 原本是ABCD 后缀是ABCDBCDCDD 在末尾加个E ABCDE 后缀变成:ABCDE,BCDE,CDE,DE,E没有一个和之前是一样的 如果是在开头加E EABCD 后缀就是EABCD,ABCD,BCD,CD,D(和原先比只多了一个EABCD我们只需要处理新增就可以) 但是题目就是让在后面加怎么搞 我们可以将这个字符串翻转呀这样每次加不就是在最前面加 原本是ABCD 翻转DCBA 加入E 得到EDCBA 新增后缀EDCBA现在我们要求新增不重复字串按照结论后缀长度减去其height[i] height[i]如何求 这时只有插入的那个新后缀紧邻的height 值发生了改变注意到这个值是可以直接在整段字符串的后缀数组中查到的即 lcp(prev(i),post(i)) 。 height[i]的变化是O(1)的我们用一个set每次插入后缀排名对于以第i位开始的后缀其排名是rk[i],他的就找他在set中的前一位(到目前位置已有后缀的前一项)再找后项两边分别取min(height[l~r])这可以用st来实现。这就是重复部分用长度len减去重复部分就是后缀的贡献 详细看代码
代码
// Problem: P4070 [SDOI2016]生成魔咒
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4070
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Data:2021-08-23 12:42:42
// By Jozky#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int MAXN 100005;char ch[MAXN], all[MAXN];
int sa[MAXN], rk[MAXN], height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m;
char str[MAXN];
int b[MAXN];
//rk[i] 第i个后缀的排名; sa[i] 排名为i的后缀位置; height[i] 排名为i的后缀与排名为(i-1)的后缀的LCP
//tax[i] 计数排序辅助数组; tp[i] rk的辅助数组(计数排序中的第二关键字),与sa意义一样。
//a为原串
void RSort()
{//rk第一关键字,tp第二关键字。for (int i 0; i m; i)tax[i] 0;for (int i 1; i n; i)tax[rk[tp[i]]];for (int i 1; i m; i)tax[i] tax[i - 1];for (int i n; i 1; i--)sa[tax[rk[tp[i]]]--] tp[i]; //确保满足第一关键字的同时再满足第二关键字的要求
} //计数排序,把新的二元组排序。int cmp(int* f, int x, int y, int w)
{return f[x] f[y] f[x w] f[y w];
}
//通过二元组两个下标的比较确定两个子串是否相同void Suffix()
{//safor (int i 1; i n; i)rk[i] a[i], tp[i] i;m 127, RSort(); //一开始是以单个字符为单位所以(m 127)for (int w 1, p 1, i; p n; w w, m p) { //把子串长度翻倍,更新rk//w 当前一个子串的长度; m 当前离散后的排名种类数//当前的tp(第二关键字)可直接由上一次的sa的得到for (p 0, i n - w 1; i n; i)tp[p] i; //长度越界,第二关键字为0for (i 1; i n; i)if (sa[i] w)tp[p] sa[i] - w;//更新sa值,并用tp暂时存下上一轮的rk(用于cmp比较)RSort(), swap(rk, tp), rk[sa[1]] p 1;//用已经完成的sa来更新与它互逆的rk,并离散rkfor (i 2; i n; i)rk[sa[i]] cmp(tp, sa[i], sa[i - 1], w) ? p : p;}//离散把相等的字符串的rk设为相同。//LCPint j, k 0;for (int i 1; i n; height[rk[i]] k)for (k k ? k - 1 : k, j sa[rk[i] - 1]; a[i k] a[j k]; k);//这个知道原理后就比较好理解程序
}
int st[MAXN][30];
void ST()
{for (int i 1; i n; i)st[i][0] height[i];int w log2(n);for (int k 1; k w; k) {for (int i 1; i n; i) {if (i (1 k) n 1)break;st[i][k] min(st[i][k - 1], st[i (1 (k - 1))][k - 1]);}}
}
int get_min(int l, int r)
{int k log2(r - l 1);return min(st[l][k], st[r - (1 k) 1][k]);
}
void Init()
{read(n);for (int i 1; i n; i) {read(a[i]);b[i] a[i];}sort(b 1, b 1 n);int len unique(b 1, b 1 n) - (b 1);reverse(a 1, a 1 n);for (int i 1; i n; i) {a[i] lower_bound(b 1, b 1 len, a[i]) - b;}
}
setint s;int main()
{Init();Suffix();ST();// for (int i 1; i n; i)// printf(height[i]%d\n, height[i]);ll ans 0;for (int i n; i; i--) { //倒序考虑s.insert(rk[i]);setint::iterator it;it s.find(rk[i]);int lcp 0;if (it ! s.begin()) { //如果没到开头说明前面有height和前面取minint p *(--it);lcp get_min(p 1, rk[i]);it; //还原}/*注意s.begin();返回指向容器最开始位置数据的指针而s.end();返回指向容器最后一个数据单元1的指针*/it;if (it ! s.end()) {int p *it;lcp max(lcp, get_min(rk[i] 1, p));}int len n - i 1;ans len - lcp;printf(%lld\n, ans);}
}
