Submission #3124028
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
/*
ある箇所から,
xもじが右側に出るなら,x以下も全部右に出る
x+1は出ないとすると,
...aがみぎに登場しないのだからx + 2文字の
...abとかも当然右に登場しない
LCP_i と i+1 , ... , i + n-1を比べたもののうちの最大値だ
つまりSA上で後ろにある場合は後ろ,
前にある場合は前方向へと考慮をして,
自分の値を使うといい(i-1とi)
もとの数列上で右からやるといい
SA上でのleft most, right mostをもっておく
*/
/// --- SA-IS {{{ ///
template < class _T = string, class U = char, int K = 256 >
struct SA {
using T = _T;
const int n;
const T &s;
vector< int > rnk;
vector< int > sa;
int operator[](int i) const { return sa[i]; }
SA(const string &s) : n(s.size()), s(s), rnk(n) {
sa_is< T, U >(sa, s + U(0), K); // change if T != string
sa.erase(begin(sa));
for(int i = 0; i < n; i++) rnk[sa[i]] = i;
}
template < class V = string, class W = char >
void sa_is(vector< int > &sa, const V &s, int k) {
int n = s.size();
vector< int > S(n); // or L
//
S.back() = 1;
for(int i = n - 2; i >= 0; i--) {
if(s[i] < s[i + 1])
S[i] = 1;
else if(s[i] > s[i + 1])
S[i] = 0;
else
S[i] = S[i + 1];
}
//
vector< int > lms;
for(int i = 0; i < n; i++)
if(isLMS(S, i)) lms.emplace_back(i);
auto seed = lms;
vector< int > _sa;
inducedSort< V, W >(_sa, s, k, S, seed);
sa.resize(0);
for(auto el : _sa)
if(isLMS(S, el)) sa.emplace_back(el);
vector< int > nums(n, -1);
int num = 0;
nums[sa[0]] = 0;
for(int x = 0; x < (int) sa.size() - 1; x++) {
int i = sa[x], j = sa[x + 1];
int diff = 0;
for(int d = 0; d < n; d++) {
if(s[i + d] != s[j + d] || isLMS(S, i + d) != isLMS(S, j + d)) {
diff = 1;
break;
} else if(d && (isLMS(S, i + d) || isLMS(S, j + d)))
break;
}
if(diff) num++;
nums[j] = num;
}
auto _nums = nums;
nums.resize(0);
for(int el : _nums)
if(el != -1) nums.emplace_back(el);
if(num + 1 < (int) nums.size()) {
sa_is< vector< int >, int >(seed, nums, num + 1);
} else {
seed.resize(num + 1);
for(int i = 0; i < num + 1; i++) seed[nums[i]] = i;
}
for(int &el : seed) el = lms[el];
inducedSort< V, W >(sa, s, k, S, seed);
}
template < class V = string, class W = char >
void inducedSort(vector< int > &sa, const V &s, int k, const vector< int > &S,
const vector< int > &lms) {
int n = s.size();
sa.resize(n), sa.assign(n, -1);
vector< int > bin(k + 1, 0);
for(W ch : s) bin[ch + 1]++;
int sum = 0;
for(int &el : bin) el = sum += el;
// step 1
vector< int > count(k);
for(auto it = rbegin(lms); it != rend(lms); ++it) {
int i = *it;
W ch = s[i];
sa[bin[ch + 1] - 1 - count[ch]] = i;
count[ch]++;
}
// step 2
count.assign(k, 0);
for(int i : sa) {
if(i == -1 || i == 0) continue;
if(S[i - 1]) continue;
W ch = s[i - 1];
sa[bin[ch] + count[ch]] = i - 1;
count[ch]++;
}
// step 3
count.assign(k, 0);
for(auto it = rbegin(sa); it != rend(sa); ++it) {
int i = *it;
if(i == -1 || i == 0) continue;
if(!S[i - 1]) continue;
W ch = s[i - 1];
sa[bin[ch + 1] - 1 - count[ch]] = i - 1;
count[ch]++;
}
}
inline bool isLMS(const vector< int > &S, int i) {
return i > 0 && !S[i - 1] && S[i];
}
};
/// }}}--- ///
// require SA
/// --- LCP Array Library {{{ ///
template < class S = SA<> >
struct LCP {
using T = typename S::T;
const int n;
const T &s;
vector< int > lcp;
int operator[](int i) const { return lcp[i]; }
LCP(const S &sa) : n(sa.n), s(sa.s), lcp(n - 1) {
int h = 0;
for(int i = 0; i < n; i++) {
if(h) h--;
if(sa.rnk[i] == 0) continue;
int j = sa[sa.rnk[i] - 1];
while(i + h < n && j + h < n && s[i + h] == s[j + h]) h++;
lcp[sa.rnk[i] - 1] = h;
}
}
};
/// }}}--- ///
int main() {
std::ios::sync_with_stdio(false), std::cin.tie(0);
string s;
cin >> s;
int n = s.size();
SA<> sa(s);
LCP<> lcp(sa);
int l = n, r = -1;
ll ans = 0;
for(int i = n-1; i >= 0; i--) {
int id = sa.rnk[i];
int res = 0;
if(l < id) if(id >= 1) res = max(res, lcp[id-1]);
if(r > id) if(id < n-1) res = max(res, lcp[id]);
l = min(l, id);
r = max(r, id);
ans += (ll) (n - i) * (n - i + 1) / 2;
ans -= (ll) res * (res + 1) / 2;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
E - 部分文字列 |
User |
luma |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5077 Byte |
Status |
WA |
Exec Time |
14 ms |
Memory |
3608 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Subtask3 |
Score / Max Score |
0 / 0 |
0 / 15 |
0 / 35 |
0 / 50 |
Status |
|
|
|
|
Set Name |
Test Cases |
Sample |
sample_1.txt, sample_2.txt, sample_3.txt |
Subtask1 |
sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt |
Subtask2 |
sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt |
Subtask3 |
sample_1.txt, sample_2.txt, sample_3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub1_7.txt, sub1_8.txt, sub1_9.txt, sub2_1.txt, sub2_2.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_1.txt |
AC |
1 ms |
256 KB |
sample_2.txt |
AC |
1 ms |
256 KB |
sample_3.txt |
AC |
1 ms |
256 KB |
sub1_1.txt |
AC |
1 ms |
256 KB |
sub1_2.txt |
AC |
1 ms |
256 KB |
sub1_3.txt |
AC |
1 ms |
256 KB |
sub1_4.txt |
WA |
1 ms |
256 KB |
sub1_5.txt |
WA |
1 ms |
256 KB |
sub1_6.txt |
WA |
1 ms |
256 KB |
sub1_7.txt |
WA |
1 ms |
256 KB |
sub1_8.txt |
WA |
1 ms |
256 KB |
sub1_9.txt |
WA |
1 ms |
256 KB |
sub2_1.txt |
WA |
1 ms |
256 KB |
sub2_2.txt |
WA |
1 ms |
384 KB |
sub3_1.txt |
WA |
2 ms |
384 KB |
sub3_2.txt |
WA |
3 ms |
1024 KB |
sub3_3.txt |
WA |
14 ms |
3608 KB |