KMP

1/3ページ

2017年09月07日提高組第一式 B

Description Alice和Bob正在悄悄地給對方發資訊,資訊都是由英文小寫字母組成的,他們約定,所有的字母都得經過一個字母表進行變換,以防洩漏。另一方面John卻在監聽。 John發現,Alice和Bob通訊的時候,總是先傳送加密後的密文,然後緊接著傳送原文。 但是Alice和Bob似乎也 […]

2017年11月2日提高組T1 Sequence

Description Input Output Hint Solution 想像一下,把點在座標系裡面描出來就能發現實際上是要找出多少段連續m個點描出的平滑曲線與b平行(意會一下)。一個簡單的方法是做一個差分陣列,kmp判斷有多少字串。差分陣列相同保證了相鄰兩點的斜率相同(口胡) 這裡寫了不太熟悉 […]

機房測試 字串 【Hash KMP】【分塊 可持久化Trie樹 貪心】【AC自動機 主席樹】

第一題 無盡的矩陣(matrix.c/cpp/pas) 題目描述 從前有一個的小矩陣,矩陣的每個元素是一個字母(區分大小寫),突然有一天它發生了變異,覆蓋了整個二維空間,即不停自我複製產生相同的矩陣然後無隙放置。現在二維空間已經被它佔領了,但你只被告知了大小為R*C空間的內容(可能包含不完整的原矩陣 […]

從頭到尾徹底理解KMP

從頭到尾徹底理解KMP 1. 引言     本KMP原文最初寫於2年多前的2011年12月,因當時初次接觸KMP,思路混亂導致寫也寫得非常混亂,如此,留言也是“罵聲”一片。所以一直想找機會重新寫下KMP,但苦於一直以來對KMP的理解始終不夠,故才遲遲沒有修改本文。     然近期因在北京開了個演算法 […]