自己的网站怎么做app,网站建设的完整流程包括哪些,wordpress主题4mudi,wordpress 关闭ajaxP2408 不同子串个数
题意#xff1a;
给你一个长为 n 的字符串#xff0c;求不同的子串的个数。
我们定义两个子串不同#xff0c;当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。
子串的定义#xff1a;原字符串中连续的一段字符组成的字符串。
题解…P2408 不同子串个数
题意
给你一个长为 n 的字符串求不同的子串的个数。
我们定义两个子串不同当且仅当有这两个子串长度不一样或者长度一样且有任意一位不一样。
子串的定义原字符串中连续的一段字符组成的字符串。
题解
对于任何一个字串一定是一个后缀的前缀所以我们可以求出用后缀数组求出LCP最长公共前缀再求出每个后缀对答案的贡献。 一个长度为n的字符串产生的字符串的个数是n(n1)/2个这是总数 现在我们开始考虑重复的情况 后缀sa[i-1]:aaabbdbs 后缀 sa[i]:aabbdbs height[i]就是2最前面两个aa是都有的是重复的说明这个重复个数正好就是height[i] 但是后面重复情况(bbdbs部分是重复)呀但其实没关系因为我们处理了所有的后缀总会有一个情况处理了bbdbs这情况。这样我们求出整个串中重复的串的个数就是∑i1nheight[i]\sum_{i1}^{n}height[i]∑i1nheight[i] 答案就是n(n1)/2-∑i1nheight[i]\sum_{i1}^{n}height[i]∑i1nheight[i] 记得开ll
代码
// Problem: P2408 不同子串个数
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2408
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Data:2021-08-22 12:24:46
// 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 1000005;char ch[MAXN], all[MAXN];
int sa[MAXN], rk[MAXN], height[MAXN], tax[MAXN], tp[MAXN], a[MAXN], n, m;
char str[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);//这个知道原理后就比较好理解程序
}void Init()
{int t;read(t);scanf(%s, str);// cout str endl;n strlen(str);for (int i 0; i n; i)a[i 1] str[i];
}
int main()
{//rd_test();Init();Suffix();ll ans 0;// for (int i 1; i n; i)// cout hei[] height[i] endl;for (int i 1; i n; i) {ans 1ll * (n - i 1) - 1ll * (height[sa[i]]);}cout ans;// for (int i 1; i n; i) {// cout rank[i] rk[i] endl;// }// for (int i 1; i n; i) {// cout hei[i] height[rk[i]] endl;// }/*aabaaabaabaaaaaaaaaabaaabaabaa*///Time_test();
}
