Weekly Problems #10
	Pedro Ribeiro - DCC/FCUP

This is one of 11 weekly problem sets. Each one is worth 10% of the grade of the "Submitted Implementation" evaluation criteria.

• Date of publication: 08/12/2025
• Date of delivery (deadline): 23h59m of 12/01/2026 (-2% for each extra day)
• Topics: Strings (KMP, Aho-Corasick, tries, suffix trees, suffix arrays)

6 proposed problems:

• [CodeForces 126B] - Password
  (tested in C++, Java and Python)
  Hints

  - Can you use KMP?

  
  
• [Mooshak PC048] - Playing Boggle
  (tested in C++, Java and Python)
  Hints

  - DFS with backtracking; you can use a trie to look for "all words" at the same time :)

  
  
• [Mooshak PC049] - Life Forms
  (tested in C++, Java and Python)
  Hints

  - Can you think on how to use suffix arrays?

  
  
• [Mooshak PC050] - Period
  (tested in C++, Java and Python)
  Hints

  - Can you think on how to adapt the KMP failure function (π)?

  
  
• [CodeForces 346B] - Lucky Common Subsequence
  (tested in C++, Java and Python)
  Hints

  - Can you combine KMP with Dynamic Programming? ;)

  
  
• [Mooshak PC051] - Passwords
  (tested in C++, Java and Python)
  Hints

  - Can you combine Aho-Corasick with Dynamic Programming? ;)

About the delivery:

• I will automatically catch your submissions from Codeforces (as well as in Mooshak).
• At the end of the semester you will need to send all your submitted code to me.
• You can chat and discuss the problems among yourselves, but you should do your own implementation (simply copying code from other or from an LLM is considered a severe break of the code of conduct).
• The final code submitted to should include comments with the temporal and spatial complexity, as well as a small explanation of your algorithmic idea. You should also refer any helps you got (including referencing any sources you have consulted).

Pedro Ribeiro - DCC/FCUP | Last update: