← Real problems

ccc03s4

easystringssuffix-arrayStatement on DMOJ

CP Lang

5 lineschecks
// ccc03s4 Substrings: the number of distinct substrings, counting the empty one. A suffix
// array counts the non-empty ones as n(n+1)/2 minus the LCP sum.
@!multitest
let s = read<Str>()
print(SuffixArray(s).distinct() + 1)

Accepted C++

186 lines · 0.08 s on the judge
#include "bits/extc++.h"

using namespace std;

template<class T>
using mpq = priority_queue<T, vector<T>, greater<>>;

template<class T, class U = less<T>>
using rt = __gnu_pbds::tree<T, __gnu_pbds::null_type, U, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

template<class T>
void dbgh(const T &t) {
	cerr << t << endl;
}

template<class T, class ...U>
void dbgh(const T &t, const U &...u) {
	cerr << t << " | ";
	dbgh(u...);
}

#ifdef DEBUG
#define dbg(...) cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]" << ": "; dbgh(__VA_ARGS__)
#else
#define cerr if(false) cerr
#define dbg(...) 1412
#endif

//imagine a language where int = long
#define long int64_t

//typing too hard
#define endl "\n"

#define sz(x) static_cast<int>((x).size())

#define inline inline __attribute__((always_inline))

template<int mod>
constexpr long bpow(long base, long exp) {
	long ans = 1;
	while(exp) {
		if(exp & 1) {
			ans = (ans * base) % mod;
		}
		base = (base * base) % mod;
		exp >>= 1;
	}
	return ans;
}

template<int mod>
constexpr long inv(long x) {
	return bpow<mod>(x, mod - 2);
}

template<int mod>
struct Hash {
	static constexpr int base = 67, ibase = inv<mod>(base);
	vector<long> pow, ipow, psum;

	Hash(const string &s) {
		int n = sz(s);
		pow.resize(n + 1);
		ipow.resize(n + 1);
		psum.resize(n + 1);
		pow[0] = ipow[0] = 1;
		for(int i = 0; i < n; i++) {
			pow[i + 1] = (pow[i] * base) % mod;
			ipow[i + 1] = (ipow[i] * ibase) % mod;
			psum[i + 1] = (psum[i] + conv(s[i]) * pow[i]) % mod;
		}
	}

	int conv(char c) {
		if(isupper(c)) {
			return c - 'A';
		}else if(islower(c)) {
			return 26 + c - 'a';
		}
		return 52 + c - '0';
	}

	long hash(int l, int r) {
		return ((psum[r] - psum[l] + mod) * ipow[l]) % mod;
	}
};

struct SA {
	static constexpr int mod1 = 1e9 + 7, mod2 = 1e9 + 9;
	int n;
	string s;
	Hash<mod1> h1;
	Hash<mod2> h2;
	vector<int> arr, l;

	SA(const string &_s): n(sz(_s)), s(_s), h1(s), h2(s), arr(n), l(n) {
		iota(begin(arr), end(arr), 0);
		sort(begin(arr), end(arr), [&](int a, int b) -> bool {
			return cmp(a, b);
		});
		for(int i = 0; i < n - 1; i++) {
			l[i] = lcp(arr[i], arr[i + 1]);
		}
	}

	bool eq(int a, int b, int len) {
		return a + len <= n && b + len <= n
			   && h1.hash(a, a + len) == h1.hash(b, b + len)
			   && h2.hash(a, a + len) == h2.hash(b, b + len);
	}

	int lcp(int a, int b) {
		int l = 0, r = n - 1;
		while(l < r) {
			int mid = (l + r + 1) / 2;
			if(eq(a, b, mid)) {
				l = mid;
			}else {
				r = mid - 1;
			}
		}
		return l;
	}

	bool cmp(int a, int b) {
		if(a == b) {
			return false;
		}
		int l = lcp(a, b);
		if(max(a, b) + l == n) {
			return a + l == n;
		}
		return s[a + l] < s[b + l];
	}
};

void solve() {
	string s;
	cin >> s;
	int n = sz(s);
	SA sa(s);
	int m = 2 * n;
	int arr[m];
	for(int i = 0; i < m; i += 2) {
		arr[i] = n - sa.arr[i / 2];
		arr[i + 1] = sa.l[i / 2];
	}
	vector<int> change[n + 1];
	for(int i = 0; i < m; i++) {
		change[arr[i]].push_back(i);
	}
	bool alive[m];
	memset(alive, 1, sizeof(alive));
	auto get = [&](int i) -> bool {
		return 0 <= i && i < m && alive[i];
	};
	int ans = 1, csz = 1;
	for(int i = 0; i <= n; i++) {
		for(auto &a: change[i]) {
			if(get(a - 1) && get(a + 1)) {
				csz++;
			}else if(!get(a - 1) && !get(a + 1)) {
				csz--;
			}
			alive[a] = false;
		}
		ans += csz;
	}
	cout << ans << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(ios::failbit);
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	int t = 1;
	cin >> t;
	for(int _ = 1; _ <= t; _++) {
		dbg(_);
//		cout << "Case #" << _ << ": ";
		solve();
	}
}