Сегодня я пыталась решить данную задачуToday I tried to solve this problem (https://codeforces.com/gym/102069/problem/J).↵
↵
↵
Вроде бы очевидно, что в данном случае можно использовать суффиксный массив, а затем с помощью бин.поиска найти все нужные подотрезки (причем за O(длины строки, которую нужно найти) проверяем, подходит ли данный подотрезок), затем использовать дерево отрезков, чтобы посчитать ответ. Однако это проходит на первых двух подгруппах (берёт 25 баллов). Есть одна проблема, она заключается в том, что там не гарантируется, что сумма всех подстрок, которые мы должны проверять, не будет превышать какую-либо константу (например, длину строки). Значит, нужно оптимизировать бинарный поиск (то есть находить нужные подотрезки за константу, меньшую, чем O(длины строки, которую нужно найти)). С помощью какой структуры данных это можно сделатьIt seems to be obvious that in this case, you can use a suffix array, and then use the bin.search for all the desired sub-sections (and during o(the length of the string to be found), check whether this sub-section is suitable), then use the segment tree to calculate the answer. However, this takes place in the first two subgroups (takes 25 points). There is one problem, it is that there is no guarantee that the sum of all the substrings that we have to check will not exceed any constant (for example, the length of the string). This means that you need to optimize the binary search (that is, find the desired sub-sections for a constant less than o(the length of the string to be found)). What data structure can be used to do this?
