網頁

2014年6月5日 星期四

POJ 1226 Substrings

想法:
    先將全部的字串依照length由小到大排序,把最短的那個字串拿來枚舉,由長到短枚舉該字串的所有substring,以sample input第二個case舉例,最短的字串為"rose",枚舉substring "rose", "ros", "ose", "ro", "os"...。
    每次枚舉到一個substring後,記得還有反轉sub_inverse,把substring和sub_inverse拿來和其他字串(除了最短的字串以外的字串)比較,這邊我是套KMP Algorithm,如果其他字串全部都找的到substring或sub_inverse的話,表示找到答案,輸出該substring的長度。