For the first subtask, brute force suffices. First loop through all prefixes of ~S~ and check which ones match a suffix of ~S~ to find all special substrings. Then for each special substring, loop through ~S~ to count the number of times it occurs.

Time Complexity: ~\mathcal{O}(N^3)~

For the last subtask, several approaches work. In this editorial, we will discuss a solution that uses the Knuth-Morris-Pratt or KMP algorithm. First, build the failure function, ~f~, of ~S~. Suppose we currently have some special substring ~T~. We can find the next smallest special substring by using the failure function using ~f(|T|-1)~ which stores the length of the longest prefix of ~T~ that is also a suffix of ~T~. And since ~T~ is a special substring, it is both a prefix and suffix of ~S~ and hence, the prefix and suffix of ~T~ will also be both prefixes and suffixes of ~S~. So ~f(|T|-1)~ can be used to recursively generate all special substrings shorter than ~T~. We can start this algorithm with ~S~ since it is always a special substring and we will be able to obtain all special substrings.

Next, we will count all occurrences of special substrings. Observe that each occurrence of the string ~T~ means that there will be one corresponding occurrence of its prefix of length ~f(|T|-1)~. We can ignore any prefix of ~T~ longer than ~f(|T|-1)~ because they aren't special substrings and are irrelevant to the answer. Also, shorter prefixes of ~T~ will be accounted for by the prefix of length ~f(|T|-1)~. Therefore we can iterate through all suffixes of ~S~ from largest to smallest. The number of occurrences of each suffix originally starts at ~1~ and we use the above observation to count all occurrences that aren't at the end of ~S~. Finally, add the occurrences of each special substring to obtain the answer.

Time Complexity: ~\mathcal{O}(N)~