--- tags: DSA --- # DSA In-class 5/18 ## Problem 1 ### 1. ``` t = t ^ T[s] ^ T[s+m] ``` ### 2. ``` T = "48763" P = "36784" ``` ### 3. ``` t = CS(t, 1) ^ CS(T[s], m) ^ CS(T[s+m], 0) ``` ### 4. ``` T = "0010" P = "0002" ``` ## Problem 2 ### 1. Func A sorts a list of strings by n th char, via counting sort. Func B calls Func A from the last character to the first, and that sorts the strings to an alphabetic order, which is in fact radix sort. ### 2. In function A, we have a nested loop that writes the characters to the string array, which is the total character count O(nL), and that gives us the complexity. Function B calls function A O(L) times, so the overall complexity is O(nL^2). ### 3. LSB is better. Because counting sort is stable, if we start with LSB, the sorted strings will naturally be in dictionary order. The last key you sort with will have the highest priority. ## Problem 3 (Programming) 要你判斷兩個句子是不是同義。 句子由字(word)組成，一個字長度為4。 word def:``(\^[0-9a-zA-Z]{4}$)`` 對於每一個compare你要輸出兩個句子是不是同義。 union會將兩個字的意思視為同義字。 ### Sample Input & Output ``` 5 compare nlnl7414 7414nlnl #Output: False union nlnl 7414 compare nlnl7414 7414nlnl #Output: True union mkmk nlnl compare nlnl7414 nlnl8787 #Output: False ```