Cerinta completa
You are given string and number .
Consider a substring of string . For each position of string mark it if there is an occurence of the substring that covers the position. More formally, position will be marked if there exists such index that: and . We will tell produce islands if all the marked positions form groups of contiguous positions.
For example, if we have a string ababaewabaq the substring aba marks the positions 1, 2, 3, 4, 5, 8, 9, 10; that is XXXXXewXXXq (X denotes marked position). We can see 2 groups of contiguous positions, that is 2 islands. Finally, substring aba produces 2 islands in the string ababaewabaq.
Calculate and print the number of different substrings of string that produce exactly islands.
Input Format
The first line contains string . The string consists of lowercase letters only. The second line contains an integer .
Output Format
Output a single integer the answer to the problem.
Sample Input
abaab
2
Sample Output
3
Explanation
All the suitable substrings are: a, ab, b.
Limbajul de programare folosit: cpp14
Cod:
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
#include <cstring>
#include <map>
#include <set>
#include <stack>
#include <utility>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int, int> pii;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ROF(i, a, b) for (int i = (b); --i >= (a); )
struct Pos {
static int id;
set<int> a;
tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> d;
int countLT(int key) { return d.order_of_key(pii(key, 0)); }
size_t size() { return a.size(); }
void insert(int i) {
a.insert(i);
auto it = a.lower_bound(i);
auto prev = it, next = it;
if (it != a.begin()) --prev;
if (it != a.end()) ++next;
if (it != prev) {
d.insert(pii{*it-*prev, id++});
if (it != next && next != a.end())
d.erase(d.lower_bound(pii{*next-*prev, 0}));
}
if (it != next && next != a.end())
d.insert(pii{*next-*it, id++});
}
void join(Pos &b) {
for (int x: b.a)
insert(x);
}
Pos() = default;
Pos(Pos &&b) {
a.swap(b.a);
d.swap(b.d);
}
Pos &operator=(Pos &&b) noexcept {
a.swap(b.a);
d.swap(b.d);
return *this;
}
};
int Pos::id = 0, n, k;
ll ans;
namespace KoAluru
{
bool *t;
int *b;
template<typename T>
void bucket(T a[], int n, int k, bool end)
{
fill_n(b, k, 0);
REP(i, n) b[a[i]]++;
if (end)
FOR(i, 1, k) b[i] += b[i-1];
else {
int s = 0;
REP(i, k)
s += b[i], b[i] = s-b[i];
}
}
template<typename T>
void plus_to_minus(T a[], int sa[], int n, int k)
{
bucket(a, n, k, false);
sa[b[a[n-1]]++] = n-1;
REP(i, n-1) {
int j = sa[i]-1;
if (j >= 0 && ! t[j])
sa[b[a[j]]++] = j;
}
}
template<typename T>
void minus_to_plus(T a[], int sa[], int n, int k)
{
bucket(a, n, k, true);
ROF(i, 0, n) {
int j = sa[i]-1;
if (j >= 0 && t[j])
sa[--b[a[j]]] = j;
}
}
template<typename T>
void ka(T a[], int sa[], int n, int k)
{
t[n-1] = false;
ROF(i, 0, n-1)
t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1];
bool minor = 2 * count(t, t+n, false) > n;
bucket(a, n, k, minor);
fill_n(sa, n, -1);
if (minor) {
REP(i, n)
if (t[i])
sa[--b[a[i]]] = i;
plus_to_minus(a, sa, n, k);
minus_to_plus(a, sa, n, k);
} else {
sa[b[a[n-1]]++] = n-1;
REP(i, n-1)
if (! t[i])
sa[b[a[i]]++] = i;
minus_to_plus(a, sa, n, k);
plus_to_minus(a, sa, n, k);
}
int last = -1, name = 0, nn = count(t, t+n, minor);
int *sa2, *pi;
if (minor)
sa2 = sa, pi = sa+n-nn;
else
sa2 = sa+n-nn, pi = sa;
fill_n(b, n, -1);
REP(i, n)
if (sa[i] >= 0 && minor == t[sa[i]]) {
bool diff = last == -1;
int p = sa[i];
if (! diff)
REP(j, n) {
if (last+j >= n || p+j >= n || a[last+j] != a[p+j] || t[last+j] != t[p+j]) {
diff = true;
break;
} else if (j > 0 && (minor == t[last+j] || minor == t[p+j]))
break;
}
if (diff) {
name++;
last = p;
}
b[p] = name-1;
}
nn = 0;
REP(i, n)
if (b[i] >= 0)
pi[nn++] = b[i];
if (name < nn)
ka(pi, sa2, nn, name);
else
REP(i, nn)
sa2[pi[i]] = i;
ROF(i, 0, nn)
t[i] = a[i] < a[i+1] || a[i] == a[i+1] && t[i+1];
nn = 0;
bucket(a, n, k, minor);
if (minor) {
REP(i, n)
if (minor == t[i])
pi[nn++] = i;
REP(i, nn)
sa[i] = pi[sa2[i]];
ROF(i, 0, nn) {
int j = sa[i];
sa[i] = -1;
sa[--b[a[j]]] = j;
}
} else {
REP(i, n)
if (minor == t[i])
pi[nn++] = i;
ROF(i, 0, nn)
sa[n-nn+i] = pi[sa2[i]];
REP(i, nn) {
int j = sa[n-nn+i];
sa[n-nn+i] = -1;
sa[b[a[j]]++] = j;
}
}
if (minor)
plus_to_minus(a, sa, n, k);
else
minus_to_plus(a, sa, n, k);
}
template<typename T>
void main(T a[], int sa[], int b[], int n, int k)
{
if (n > 0) {
KoAluru::b = b;
t = new bool[n];
ka(a, sa, n, k);
delete[] t;
}
}
template<typename T>
void calc_rank_lcp(T a[], int sa[], int n, int rank[], int lcp[])
{
REP(i, n)
rank[sa[i]] = i;
int k = 0;
lcp[0] = 0;
FOR(i, 0, n)
if (rank[i]) {
for (int j = sa[rank[i]-1]; i+k < n && j+k < n && a[i+k] == a[j+k]; k++);
lcp[rank[i]] = k;
k && k--;
}
}
void calc_child(int lcp[], int n, int child[]) {
stack<int> st;
st.push(0);
int last = -1;
fill_n(child, n, -1);
FOR(i, 1, n) {
while (lcp[i] < lcp[st.top()]) {
last = st.top();
st.pop();
if (lcp[i] <= lcp[st.top()] && lcp[st.top()] != lcp[last])
child[st.top()] = last;
}
if (last != -1) {
child[i-1] = last;
last = -1;
}
st.push(i);
}
while (0 < lcp[st.top()]) {
last = st.top();
st.pop();
if (0 <= lcp[st.top()] && lcp[st.top()] != lcp[last])
child[st.top()] = last;
}
while (! st.empty())
st.pop();
st.push(0);
FOR(i, 1, n) {
while (lcp[i] < lcp[st.top()])
st.pop();
if (lcp[i] == lcp[st.top()]) {
child[st.top()] = i;
st.pop();
}
st.push(i);
}
}
void top_down(int sa[], int lcp[], int child[], int l, int h, int ht, Pos &data)
{
int ht2;
if (l == h-1) {
ht2 = n-sa[l];
data.insert(sa[l]);
} else {
int i = l < child[h-1] && child[h-1] < h ? child[h-1] : child[l];
ht2 = lcp[i];
{
Pos cur;
top_down(sa, lcp, child, l, i, ht2, cur);
if (cur.size() > data.size()) swap(cur, data);
data.join(cur);
}
for (; child[i] > i && lcp[child[i]] == lcp[i]; i = child[i]) {
Pos cur;
top_down(sa, lcp, child, i, child[i], ht2, cur);
if (cur.size() > data.size()) swap(cur, data);
data.join(cur);
}
{
Pos cur;
top_down(sa, lcp, child, i, h, ht2, cur);
if (cur.size() > data.size()) swap(cur, data);
data.join(cur);
}
}
l = ht+1;
h = ht2+1;
while (l < h) {
int mi = l+h >> 1;
if (k < data.size()-data.countLT(mi+1))
l = mi+1;
else
h = mi;
}
int from = l;
h = ht2+1;
while (l < h) {
int mi = l+h >> 1;
if (k <= data.size()-data.countLT(mi+1))
l = mi+1;
else
h = mi;
}
ans += l-from;
}
};
const int N = 100000;
char a[N+1];
int b[N], sa[N], rnk[N], lcp[N], child[N];
int main()
{
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
scanf("%s%d", a, &k);
n = strlen(a);
KoAluru::main(a, sa, b, n, 127);
KoAluru::calc_rank_lcp(a, sa, n, rnk, lcp);
KoAluru::calc_child(lcp, n, child);
Pos data;
KoAluru::top_down(sa, lcp, child, 0, n, 0, data);
printf("%lld\n", ans);
}
Scor obtinut: 1.0
Submission ID: 464646973
Link challenge: https://www.hackerrank.com/challenges/letter-islands/problem
Letter Islands