Substrings SPOJ - NSUBSTR （后缀自动机）

心已赠人 2021-11-09 23:10 231阅读 0赞

# Substrings #

\\\[ Time Limit: 100ms\\quad Memory Limit: 1572864 kB \\\]

## 题意 ##

给出一个长度为 \\(250000\\) 的字符串，求出所有 \\(x\\) 的 \\(F(x)\\) 。  
\\(F(x)\\) 含义为长度为 \\(x\\) 的子串出现的最多次数。

## 思路 ##

先对给出的串构建后缀自动机，设 \\(dp\[i\]\\) 为后缀自动机上节点 \\(i\\) 包含的最长子串的出现的次数。那么对于主链的上的点，可以直接赋初始值 \\(dp\[i\] = 1\\)，也就是从根节点直接走到当前节点。  
对于任意节点 \\(i\\) ，\\(i\\) 中出现的子串必定也会在其 \\(father\\) 上出现，所以我们可以得到

dp[father] += dp[i]。

如此就可以计算出节点 \\(i\\) 的子串的出现次数，得到

anslen[node[i].len] = max(anslen[node[i].len], dp[i]);

现在求出的是对于每个节点上 \\(maxlen\\) 的 \\(anslen\\)，对于 \\(\\left\[minlen，maxlen-1\\right\]\\) 范围内还没有求出来，所以我们还要在更新一遍。  
因为长度更短的子串一定包括在长度更长的子串中，所以可以得到

anslen[i] = max(anslen[i], anslen[i+1]);

最后输出\\(anslen\\)就是题目的\\(F(x)\\)。

#include <map> #include <set> #include <list> #include <ctime> #include <cmath> #include <stack> #include <queue> #include <cfloat> #include <string> #include <vector> #include <cstdio> #include <bitset> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define lowbit(x) x & (-x) #define mes(a, b) memset(a, b, sizeof a) #define fi first #define se second #define pii pair<int, int> #define INOPEN freopen("in.txt", "r", stdin) #define OUTOPEN freopen("out.txt", "w", stdout) typedef unsigned long long int ull; typedef long long int ll; const int maxn = 3e5 + 10; const int maxm = 1e5 + 10; const ll mod = 1e9 + 7; const ll INF = 1e18 + 100; const int inf = 0x3f3f3f3f; const double pi = acos(-1.0); const double eps = 1e-8; using namespace std; int n, m; int cas, tol, T; struct SAM { struct Node{ int next[27]; int len, fa; void init() { mes(next, 0); len = fa = 0; } } node[maxn<<1]; vector<int> vv[maxn<<1]; int dp[maxn<<1], anslen[maxn]; int sz, last; void init() { sz = last = 1; node[sz].init(); mes(dp, 0); mes(anslen, 0); } void insert(int k) { int p = last, np = last = ++sz; node[np].init(); dp[np] = 1; node[np].len = node[p].len+1; for(; p&&!node[p].next[k]; p=node[p].fa) node[p].next[k] = np; if(p==0) { node[np].fa = 1; } else { int q = node[p].next[k]; if(node[q].len == node[p].len + 1) { node[np].fa = q; } else { int nq = ++sz; node[nq] = node[q]; node[nq].len = node[p].len+1; node[np].fa = node[q].fa = nq; for(; p&&node[p].next[k]==q; p=node[p].fa) node[p].next[k] = nq; } } } void dfs(int u) { for(auto v : vv[u]) { dfs(v); dp[u] += dp[v]; } anslen[node[u].len] = max(anslen[node[u].len], dp[u]); } void solve(int len) { for(int i=1; i<=sz; i++) { vv[i].clear(); } for(int i=2; i<=sz; i++) { vv[node[i].fa].push_back(i); } dfs(1); for(int i=len-1; i>=1; i--) { anslen[i] = max(anslen[i], anslen[i+1]); } for(int i=1; i<=len; i++) { printf("%d\n", anslen[i]); } } } sam; char s[maxn]; int main() { scanf("%s", s+1); sam.init(); int len = strlen(s+1); for(int i=1; i<=len; i++) { sam.insert(s[i]-'a'+1); } sam.solve(len); return 0; }

转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/10904814.html