Нахождение K-й лексикографически подстроки заданной строки, когда разрешены повторяющиеся подстроки
я хочу найти лексикографически Kth самая маленькая подстрока данной строки, когда допускаются повторяющиеся подстроки.
Предположим, нам дана строка азбука тогда его подстроки в лексикографическом порядке: {a, ab, abc, b, c}, теперь предположим, что нам дано K = 3, тогда ans is азбука.
Теперь предположим, что нам дана строка ааа тогда все его подстроки {А, а, а, аа, ааа, аа} так что теперь, если K = 4, то мы выводим аа.
Однако я наткнулся на следующий код на Codeforces но я не могу этого понять. любая помощь очень ценится.
char s [MaxN];
bool b [MaxN];
int k, n;
void solve (vector <int> v)
{
int i, j;
int64 p, q;
char c;
vector <int> w;
for (c = 'a'; c <= 'z'; c++)
{
p = q = 0;
w.clear ();
for (j = 0; j < (int) v.size (); j++)
{
i = v[j];
if (s[i] == c)
{
w.push_back (i + 1);
p++;
q += n - i;
}
}
if (k < q)
break;
k -= q;
}
assert (c <= 'z');
putchar (c);
if (k < p)
return;
k -= p;
solve (w);
}
int main (void)
{
int i;
while (scanf (" %s %d", s, &k) != EOF)
{
n = (int) strlen (s);
if (k > ((((int64) n) * (int64) (n + 1)) >> 1LL))
{
printf ("No such line.\n");
continue;
}
k--;
vector <int> v;
for (i = 0; i < n; i++)
v.push_back (i);
solve (v);
putchar ('\n');
}
return 0;
}
Вот ссылка на вопрос http://codeforces.com/problemset/problem/128/B
Решение
Стандартный подход к этой проблеме состоит в создании массива суффиксов для данной строки. Суффиксный массив дает нам все суффиксы данной строки в лексикографически отсортированном порядке. Как только у нас есть все отсортированные суффиксы данной строки, обратите внимание, что каждая подстрока строки является префиксом некоторого суффикса. И если мы пересмотрим суффиксы в лексикографическом порядке возрастания для каждого суффикса размера l, мы получим l подстрок, каждая из которых меньше, чем подстроки, полученные из суффиксов, которые по лексикографическому союзу больше, чем суффикс, который мы рассматриваем , Таким образом, мы можем легко найти K-ю самую маленькую подстроку путем маринования количества подстрок.
Фактически массив суффиксов используется для решения более сложной версии этой проблемы, где вам задают Q запросов для поиска K-й подстроки, где K отличается в каждом запросе.
Что касается кода, который вы задали в вопросе, поскольку вы должны найти k-ю подстроку только один раз, подход к решению по существу использует ту же логику, но с другой реализацией.
Другие решения