GSLC - CP - Session 4
Instructions: Answer the theory question below (required), plus at least 2 of the 4 coding questions (more is welcome). The coding questions are real Codeforces problems, solve and submit them there, then paste your submission link in your reply on the Binus Maya forum (open your Status page on Codeforces, click your submission, and copy the URL).
Theory Question - KMP Failure Function Tracing
Given the pattern P = "abababc", compute the failure function F(i) for every index i from 0 to 6 (the length of P is 7), following the method shown in the slides (longest matching prefix vs. suffix).
Write out the full table, and specifically explain:
a) Why F(5) = 4 - why does the value keep climbing up to this point?
b) Why F(6) = 0 even though F(5) was fairly large - what causes the sharp "drop" to 0 at the last index?
Coding Question 1 - Entry Level
CF 112A — Petya and Strings 🔗 https://codeforces.com/problemset/problem/112/A
Compare two strings lexicographically, case-insensitive. Print -1 if the first string is smaller, 1 if it's larger, 0 if they're equal.
Coding Question 2 - Entry-Medium
CF 58A — Chat room 🔗 https://codeforces.com/problemset/problem/58/A
Given a string, check whether the word "hello" appears in it as a subsequence (the letters don't need to be consecutive, but their relative order — h, e, l, l, o — must be preserved). Print YES or NO.
Coding Question 3 - Medium
CF 1029A - Many Equal Substrings 🔗 https://codeforces.com/problemset/problem/1029/A
Given a string t (length n) and an integer k, construct the shortest possible string s such that t appears as a substring exactly k times within s.
Hint: use the failure function of t to find the "overlap" part that can be reused when repeating t.
Coding Question 4 - Advanced
CF 126B - Password 🔗 https://codeforces.com/problemset/problem/126/B
Given a string s, find the longest substring t that satisfies all three conditions at once:
tis a prefix ofs,tis a suffix ofs,talso occurs somewhere insides(not just as the prefix/suffix occurrence itself).
If no such substring exists, print Just a legend.
This is a classic KMP application — you'll need to walk the "border chain" (F(i), then F(F(i)-1), and so on down to 0) and check, for each border length, whether it also occurs ending somewhere before the very last character of s.