Boring counting
[Time Limit: 1000 ms quad Memory Limit: 32768 kB
]
题意
给出一个字符串，求出其中出现两次及以上的子串个数，要求子串之间不可以重合。
思路
在 (SAM) 上对于节点 (i) ，其包含的子串长度范围为 (left[maxlenleft(father ight)+1，maxlenleft(i ight) ight])，在考虑节点(i)的 (endpos)，设出现的最左位置为 (left)，最右位置为 (right)，如果我们可以得到 (left) 和 (right)，我们就可以进行如下的讨论：
- 首先明确 (right-left) 是同一子串两次出现位置最大距离，我们考虑在这个距离中，可以不重合的放下多少子串。
-
若 (right-left geq maxlen(i))，距离足够大放下节点 (i) 可以表示的最长子串。这说明对于节点 (i) 包含的所有子串，都能满足不重合的出现两次。一共有 (maxlen(i)-maxlen(father)) 种子串符合条件。
-
若 (right-left leq maxlen(father))，此时距离太小，无法放下节点 (i) 可以表示的最短子串。这说明对于节点 (i) 包含的所有子串，都无法满足不重合的出现两次。
-
若 (maxlen(father) < right-left < maxlen(i))， 此时距离只够放下其中的一部分子串。这时候容易得到，可以放下的子串的长度范围为 (left[maxlen(father)+1，right-left ight])，也就是有 (right-left-maxlen(father)) 种子串符合条件。
综合上面三种情况，整理起来就是
- 若 (right-left leq maxlen(father))，对答案贡献0。
- 否则，对答案贡献 (min(right-left，maxlen(i)) - maxlen(father))。
那么如何得到 (left)和(right)？
- 对于 (left)，每个子串第一次出现的位置，一定就是他的 (left)。
- 对于 (right)，因为 (endpos(i) in endpos(father))，所以将每个节点的 (left) 往其 (father) 上更新最大值，就是 (father) 的 (right)，如此倒着求 (right)。
/***************************************************************
> File Name : a.cpp
> Author : Jiaaaaaaaqi
> Created Time : 2019年05月23日 星期四 00时06分46秒
***************************************************************/
#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>
typedef unsigned long long int ull;
typedef long long int ll;
const int maxn = 1e3 + 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 fa, len;
int left, right;
void init() {
mes(next, 0);
fa = len = left = right = 0;
}
} node[maxn<<1];
vector<int> vv[maxn<<1];
int sz, last;
void init() {
sz = last = 1;
node[sz].init();
}
void insert(int k, int id) {
int p = last, np = last = ++sz;
node[np].init();
node[np].len = node[p].len + 1;
node[np].left = node[np].right = id;
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[nq].left = node[q].left;
node[nq].right = node[q].right;
node[np].fa = node[q].fa = nq;
for(; p&&node[p].next[k]==q; p=node[p].fa)
node[p].next[k] = nq;
}
}
}
bool vis[maxn<<1];
void dfs(int u) {
if(vis[u]) return ;
vis[u] = true;
for(auto v : vv[u]) {
dfs(v);
node[u].right = max(node[u].right, node[v].right);
}
}
void build() {
for(int i=1; i<=sz; i++) vv[i].clear();
for(int i=2; i<=sz; i++) {
vv[node[i].fa].push_back(i);
}
mes(vis, 0);
dfs(1);
}
int finalans;
void DFS(int u) {
if(vis[u]) return ;
vis[u] = true;
for(auto v : vv[u]) {
DFS(v);
int l = node[v].left, r = node[v].right;
if(r-l > node[u].len) {
finalans += min(node[v].len, r-l) - node[u].len;
}
}
return ;
}
int solve() {
finalans = 0;
mes(vis, 0);
DFS(1);
return finalans;
}
} sam;
char s[maxn];
int main() {
while(scanf("%s", s+1)) {
if(s[1] == '#') break;
sam.init();
int len = strlen(s+1);
for(int i=1; i<=len; i++) {
sam.insert(s[i]-'a'+1, i);
}
sam.build();
// for(int i=1; i<=sam.sz; i++) {
// printf("%d left = %d right = %d
", i, sam.node[i].left, sam.node[i].right);
// }
printf("%d
", sam.solve());
}
return 0;
}