網頁

顯示具有 KMP Algorithm 標籤的文章。 顯示所有文章
顯示具有 KMP Algorithm 標籤的文章。 顯示所有文章

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的長度。

POJ 3461 Oulipo

題意:
    找出W字串在T字串中出現幾次。例如W="AZA",T="AZAZAZA",答案為3次。

想法:
    套KMP演算法