dutinmeow's blog

By dutinmeow, history, 4 weeks ago, In English

I've seen CF tutorials for many other sections of CSES but didn't see one for strings, so I thought of writing one. Constructive criticism (or just regular criticism) is always welcome!

Note that there are many ways to do a problem. For instance, linear time string searching can be done with hashing, KMP, Z-Algorithm, Aho-Corasick Automaton, etc. . I used the way that was most intuitive for me, but there might exist other ways that have shorter code.

1. Word Combinations

Solution
Code

2. String Matching

Solution
Code

3. Finding Borders

Solution
Code

4. Finding Periods

Solution
Code

5. Minimal Rotation

Solution
Code

6. Longest Palindrome

Solution
Code

7. Required Substring

Solution
Code

Solution and Code from nohaxjustsoflo

8. Palindrome Queries

Solution
Code

9. Finding Patterns

Solution
Code

10. Counting Patterns

Solution
Code

11. Pattern Positions

Solution
Code

12. Distinct Substring

Solution
Code

13. Repeating Substring

Solution
Code

14. String Functions

Solution
Code

15. Substring Order I

Solution
Code

16. Substring Order II

Solution
Code

17. Substring Distribution

Solution
Code

Solution and Code for Required Substring coming soon!

 
 
 
 
  • Vote: I like it
  • +103
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The code for counting patterns isn't formatted correctly.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +16 Vote: I do not like it

I thought I ought to mention that Substring Order 1, Substring Order 2, and Substring Distribution all have a suffix array + lcp solution as well.

Substring Order 1

Consider the solution for counting all the unique substrings, you take the sum of all lcp[i]. In the same manner you can loop over all the unique substrings in lexicographical order. Consider the suffix array, if we look at all substrings that start at the index of the start of the suffix (or sa[i]), the ones that have already be counted are the substrings in the longest common prefix of the current suffix and the suffix before it. This is by the definition of lcp[i]. So you can do pie and get that the amount of unique substrings sa[i] contributes is n — sa[i] — lcp[i] (with some off by 1's of course). A scuffed implementation can be found here.

Substring Order 2

This solution revolves around the fact that the sum of lcp[i] is linear. There are two cases to consider: 1) the answer substring appears more than once in the string, 2) the answer substring does not. For case 2, we can refer to the solution for Substring Order 1, but for case 1, its a little harder. So for some sa[i] we have all the substrings that start at sa[i] and have length <= lcp[i]. Let's try to think about how many times exactly each of these strings appear. Since we have lcp(i, h) >= lcp(i, j) for any i < h < j (and lcp returns the length of the longest common prefix of the two suffixes), we can see that binary search can be done on how many times this substring appears. We start at index sa[i] and binary search on the last time lcp(sa[i], sa[j]) >= the length of the substring we are looking at. What is the complexity of such an algorithm? It is actually still O(nlogn). To avoid double counting, we should only count the contribution of a string if and only if lcp[i] >= lcp[i-1] (since that means its the first time the substring is lexicographically smallest). For the rest of the substrings, we can use the n — sa[i] — lcp[i] trick from Substring Order 1. I am not even going to try and say this implementation is good, but here it is.

Substring Distribution

This problem again relies on the fact that the contribution of unique strings from some suffix sa[i] is n — sa[i] — lcp[i]. So for some given suffix it will contain unique substrings of lengths lcp[i]+1 to sa[i]. Using the psum[l]++, psum[r]-- trick, we have an algorithm with linear complexity with the suffix array construction aside. A scuffed implementation can be found here.

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by dutinmeow (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

why r u so orz? (っ °Д °;)っ

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I need solution problem special string. Can you help me?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks you so much. But it only have code, you can give me tutorial for this problem

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This problem can be seen as an extension of prefix sums. Run a prefix sum on the string, keeping track of an array of length 26 which is the number of occurrences of each letter. If the current prefix contains all letters in the string and each letter occurs an equal number of times, it is a valid substring. Because each substring can be represented as a differences of prefixes, we find the number of previous prefixes where the excess elements are in excess the exact same amount.

        For instance, at the current prefix, we have: a: 4 b: 3 c: 2 d: 2 e: 2 ...

        We have to find the number of previous prefixes where a is +2 and b is +1. a: +2 b: +1 c: 0 d: 0 e: 0 ...

        This is where having a map comes in handy. The mentioned solution uses a map of vectors, although an array<int, 26> would probably work better.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :O

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

7. Required Substring:

Solution:
Code:
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for the solution! Do you mind if I attribute this to you and move this up to the main post?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could someone help I am getting WA at palindromic queries with hashing + fenwick tree the link to question palindromic queries and the link to solution

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

All of those are solvable using hashing, except the first one, which has a simpler solution using Trie.

Short

P.S. Maybe except the 7the one also, I'm not sure.