后缀数组
要求统计出现两次以上不重叠的子串，其实就是统计出现两次以上不重叠的后缀的前缀，不难想到height数组。
相邻的后缀只有包含和被包含关系，或者不在同一块内，重复出现的前缀肯定在这块的height里，所以我们统计连续块内最小和最大的sa相减判断是否满足条件即可。
#include#define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;using LL = long long;inline int lowbit(int x){ return x & (-x); }inline int read(){ int ret = 0, w = 0; char ch = 0; while(!isdigit(ch)){ w |= ch == '-', ch = getchar(); } while(isdigit(ch)){ ret = (ret << 3) + (ret << 1) + (ch ^ 48); ch = getchar(); } return w ? -ret : ret;}template inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 2000;string s;LL ans;namespace SuffixArray{ string s; int sa[N], t[N], t2[N], c[N], rank[N], height[N]; void build(int m, int n){ int *x = t, *y = t2; for(int i = 0; i < m; i ++) c[i] = 0; for(int i = 0; i < n; i ++) c[x[i] = s[i]] ++; for(int i = 0; i < m; i ++) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; i --) sa[--c[x[i]]] = i; for(int k = 1; k <= n; k <<= 1){ int p = 0; for(int i = n - k; i < n; i ++) y[p++] = i; for(int i = 0; i < n; i ++){ if(sa[i] >= k) y[p++] = sa[i] - k; } for(int i = 0; i < m; i ++) c[i] = 0; for(int i = 0; i < n; i ++) c[x[y[i]]] ++; for(int i = 0; i < m; i ++) c[i] += c[i - 1]; for(int i = n - 1; i >= 0; i --) sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1, x[sa[0]] = 0; for(int i = 1; i < n; i ++){ x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && sa[i - 1] + k < n && sa[i] + k < n && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p ++; } if(p >= n) break; m = p; } int k = 0; for(int i = 0; i < n; i ++) rank[sa[i]] = i; for(int i = 0; i < n; i ++){ if(!rank[i]) continue; if(k) k --; int j = sa[rank[i] - 1]; while(s[i + k] == s[j + k]) k ++; height[rank[i]] = k; } }}using SuffixArray::build;using SuffixArray::sa;using SuffixArray::height;bool solve(int k){ bool good = false; int l = INF, r = 0; for(int i = 1; i < s.size(); i ++){ if(height[i] >= k){ l = min(l, min(sa[i], sa[i - 1])); r = max(r, max(sa[i], sa[i - 1])); } else{ if(r - l >= k) ans ++, good = true; l = INF, r = 0; } } if(r - l >= k) ans ++, good = true; return good;}int main(){ __fastIn; while(cin >> s && s != "#"){ SuffixArray::s = s; build(128, (int)s.size()); ans = 0; for(int i = 1; i <= (s.size() + 1) / 2; i ++){ if(!solve(i)) break; } cout << ans << endl; } return 0;}