租房功課

最近確認要在台北找房，但我又是初學者，所以也不太清楚要注意甚麼。這邊就把我從 0開頭學到的打出來。

第一步：確認自己的需求

就我來說，一開始是不清楚的，先找了獨立套房，後面找了分租套房，然後學到了行情價，再以行情價去出發。然後確認了朋友要加入，談起過後要「2房1廳至少1衛」，必要的設施要哪些，位置在哪，開價有二萬的心理準確。能否接受仲介抽取的準備？

第二步：鎖定特定物件

當有一個方向之後，就可以隨時去注意是否有新的物件出現。在流動率快的地方如台北，就會有很多機會冒出，好的且夠划算的，很容易只出現一二天就被搶下了。

這個階段，為了盡可能避免踩雷，要注意以下的幾點

  • 房屋照片是否有清楚拍出所有格式、
  • 管理費、電費、清潔費、水費、第四台的計算方式。
  • 產權與維修的問題
  • 上惡房東現行網搜尋，並調查周圍設施
  • 使用「房屋檢核表」去條列式檢查所有項目。
第三步：快但又確實有可能嗎？

對房東而言，沒有租出去、空租就是虧，流動性高也是不利之處。為了「利益」，可能會隱藏一些不利的資訊，又或是一直催促秒簽，不給定金就不代看，讓人在壓力之下，或是簽下去才發現。

一般而言，若真的照嚴謹的「SOP」去考驗房東，要把一些品質不良的去掉很容易，但相對自己也要去花時間去了解。什麼雨天看屋、晚上看屋，對於一個工作在身的人，那是不容易去做確實。又是像我，住很遠，也沒有辦法去看。

書上或房屋網教的是一回事，但很不巧，現實情況難照辦法走理想的流程。人事時地物未必那麼配合，除非買房，不然在高流動率的租房市場，這些功課做了，搞不好人家已經租出去了。

經驗值是有差的，假設是租屋經驗好，自然不會像新手那麼跌跌撞撞，當有一些好東西或正當的房東，很快就能做對的決定，也會做好對應的準備，不像新手要慢慢摸。

第四步：時間拉長，不要倉促

經驗值跟好物件是需要時間等待，如果有要「溝通」，那也需要時間去慢慢來，至少要一二個月，才不會被時間壓力逼得下一個心理不舒服的決定。

像我可能會到異地工作，距離工作開始的時間是不到一個月的，所以不會有太多經驗值。若一次簽一年，可能第一個月就因為當初沒有謹慎評估而後悔。

先找一個可短租的，如一個月或三個月，然後在租約的最後一個月內，去找到下一個更長期的並簽下做接交。短租若遇到不好的，如果不是重大問題，忍一下就能撐到到期並拿回押金。

第五步：花錢消災

「一分錢、一分貨」這是普遍的現象，預算再加高，就能去 讓自己有更多的選擇，以及得到更好的服務品質。到了一定的水準，就能擺脫很多的不確定，因為$$幫你解決了你的所有困擾。

2020-06-30 WordPress轉移作業

為什麼要轉移？

因為 blogger 使用上很陽春，而且日益增加的文章讓 blogger 整理不是那麼容易。相較之下 WordPress 在外觀上大勝，也有更容易上手的界面，改版後的 blogger 反而在某些輸給了舊版。

不好用，我也沒有想說要花很多時間在學習這個上，更重要的，似乎在那裡已經沒有流量會去了，AD也被停權掉。QQ

工作計劃

目前本人工作已經有了一個方向，所以也不用漫無目的去針對各家可能去做準備。

在近期的每日作業為以下

  • 每天以 10 篇文章正常化為主，也把格式、標籤做一致化。
  • 放上一些個人 github、blog’s youtube、repl.it，將作品放上。
  • 嘗試美化(?)

預期七月底完成。

今日的使用心得

我去借閱電子書，書中教把電腦當 server ，但我沒有上手，最後還是用網路版的。

網路版的最大缺點就是「慢」，有夠慢，但如果只做內容產出，就還好。

在一些排版，只有一點基礎，也能快速上手，文章比起 blogger 更好看。

等會要去清掉不小心安裝的不必要程式，希望換到這裡就能衝起人氣~

最近的規劃

目前有一些要學習，關於CCIE，就目前來看走向不是主力，很大機會拋掉，但CCNP是已經洗下頭，所以一定會去考到手。

所以關於CCNA跟CCNP的學習是一定會完成的，弄完之後，半年維護，跟原計畫是一樣的。
看了很多文章，但心裡也沒有底到底真的會遇到怎樣程度？還是誇張了點？我看事情是很淡的，所以不一定會有那麼深的感受。如果我是客戶，一定是很要求，想著錢砸下去了，給我弄好就是了。
走SI，會不會是我一輩子的路？不好說，到三十歲以前的境遇，才會決定之後的方向，現在還沒發生，所以也不會太過擔心。
比較希望有機會能去接觸大型建置案件，我覺得這算是「成就感」。有辦法去應需求去建網路，有很多領域都要跨足，還要領導其他人跟部門，那是不簡單的事，獨當一面。

先不要想那麼多，有一些抉擇要做，以下倒是有比較明確的目標。
1. 英文口語對談，終結我英文不好的惡夢，我超級討厭這種沒自信的感覺。
2. 把CCNP考完，但應該不會放在主力學習，分配時間少一些。
3. 學習Linux，許多設備系統使用Linux，筆電買好一點，開虛擬機玩。
4. 精美這個blog，或是轉到wordpress上，多寫一點學習歷程，台灣在這一塊實在欠缺。
三十歲之後看要不去上個在職專班，把學歷弄得好看一點。
走軟體雖然薪資高，不過我也不知道要怎麼切入，但軟體給我的印象就是練會了，就很難再有所突破，功績也很難去讓一般人能理解，如我寫了XXX軟體。如果走網路建置，有能力接越大，成就感越大，當然這很吃個人本事，把事蹟拿出來說嘴，像是哪家單位的網路是我家建的，大家也比較好懂。
成就感跟$$，在我心中的份量，似乎不是$$明顯勝出。
經過第一次面試的洗禮，漸漸也不是那麼畏懼工作，大學四年也壓根沒有想過那麼多，我覺得是那時欠缺環境，就沒有說可以那麼完美地在那時候就走在路上。畢業後兩年的空窗，其實找回了單純認真的態度，也把一些相當實用的雜技點好，效益可能在四十歲的時候才充分體現。
關於「菁英」這兩字，也在一些公司自介中看見，菁英到底是甚麼？很厲害？學習能力厲害？又還是很自傲？菁英如果是別人給的，那沒話說，但如果是自己貼自己「菁英」標籤，那會是一個怎樣的文化？我覺得這可能會聚集二種性質不同的菁英，一種讓你得到很大的幫助、正向的，另一種讓你痛苦、自卑的。我想在，也只能在第一種，第二種的光一眼就知道，也不會想去。
對我來說，個人傾向致力「去菁英」化，要表現得和藹可親，也不會歧視任何人。菁英一詞只能由別人對自己的能力讚賞，或是成績單上是 top 10 去說服人。每次我想說自己是專業，都覺得很心虛。擅長也不知道是什麼，因為沒有一個公用的衡量標準，沒有比較，感覺很像嘴砲居多。

遭遇網路 Flapping

關於 Flapping ，查英文翻譯是「拍打」，一直拍打？第一時間我也沒有理解。

隨後得知 Flapping 是 up down up down 也就是斷斷續續，有時通有時不通。為什麼會發生「Flapping」至今還沒有真的理解發生的原因。
畢竟這只是一種現象，會導致這個現象的原因不只一個，可能每次發生時的問題根源都不一樣，上一次能行的辦法，下一次就不見得行的通。
最近遭遇兩次Flapping，相當棘手，還是沒有那種掌握住的感覺。

第一次是在GNS3做OSPF，前第一輪也是放上數台互接，沒事，但第二輪要做 summary 的設定，就有斷斷續續的狀況，neighborship就像吵架復合反覆的情侶。一查，發現有一台 router 用 half duplex，但也奇怪，其他也是一樣的型號，不過卻是 full duplex。
一條 half duplex 造成 flapping 我可以理解，不過手動改回 full duplex，依舊沒有辦法解決 flapping ，接下來又有事，所以就沒能修到好。
第二次是今天，我重新整理家裡的LAN，由於之前不是我設，而且密碼也不是我訂也猜不出來，就重置那些不知道密碼的 router，重新設定過。
某些廠商的Router預設 Local IP Address 是 192.168.0.1，因此我建議要把入口的 router 避開使用這個位置，改成 192.168.0.254 也好，就是不要用 Default。不然一裝下去，IP Address重壘，然後大家都沒網路用 QQ。
把重壘的IP Address一改，網路就好了，不過那些裝置連到新 router 的 wifi 的要關了 wifi 再開，重新連線。如果沒有，那些手機的 gateway 是舊的AP IP  address，當然沒辦法上網。
Router 預設是 Wireless Router Mode，我家有四台 router，除了電信業者的那台之外，其它的也只是充當AP使用，都調成 AP mode 會是最有效率的。(不過也不是很重要，因為網速不高，就算到最大網速，大概用不到一半或 5% 的線路頻寛。)
一調成 AP mode 就發生 Flapping，沒有紀錄什麼 log，表面看起來好好，但是卻一直斷斷續續。
趁著離峰時刻，把設計都照預期更改，Flapping 發生，不怕斷到家人網路被罵，就能好好一步步去釐清。
最後，只是把一個線換個port就好。照理想狀況，設定值是確認沒問題，那為什麼換個port接就好？因為照家用型的設計，有一個WAN port跟數個LAN port。在AP mode下，每個port應該都是沒有區別的。
不過那台路由器的AP mode，似乎就沒有真正的平等以待。雖然它的說明說都一樣，但又提到上行路由器，這又讓人感覺是需要接到特定的port，也就是 WAN port，所以想到要把線換去那個Port，也一接就好了。(接觸不良或port壞掉也都有可能)
不過我買很久的ASUS router的 AP mode就真的是沒有差的。
至今Flapping，沒辦法用理論所學去解釋出真的原因，只猜但沒有確實到就結束了。

Virtual Routing and Forwarding(VRF) 學習

在 Router 設定的時候，介面的網段是不能夠重壘的，如果重壘會跳出警示。

在某些型號的 Router 如 7200 可以啟用 Virtual Routing and Forwarding (VRF)，可以當作產生一份虛擬的 routing table，跟本來的 global routing table 做出區隔。
使用 VRF ，可以在不同的介面上設定相同的IP位置，就像 VLAN 可以用邏輯上去區隔出不同LAN。於是我可以 1號介面設 10.1.1.1/24，同時用VRF在 2號介面設 10.1.1.1/24，不論接 1 或 2，都能ping通 10.1.1.1。
至於VRF的應用，就我初步來看可以做到 load sharing ，VRF也可以使用 Routing Protocol ，規劃好可以分割 routing table ，減少維護的難度吧(？)。總之先記錄一下。
之後再更多補充。 

Multiple Spanning-Tree Protocol (MSTP) 設定

對於Multiple Spanning-Tree Protocol的練習可以先看這裡。

關於Multiple Spanning Tree Protocol的設定，有一項要注意，要設定「 truck port」，這是指南沒寫，第一項連結也沒寫到的部分。
至於更詳細的設定或實作，我想等CCNP考完再補。
先做提醒。

GNS3的分頁式終端機軟體第二選擇 — Super-Putty

跟 GNS3 一起搭配的終端機軟體 Solar-Putty，本身是可以分頁的，也就是可以把GNS3開啟的telnet等集中在同一個視窗。

用過 Packer Tracer 的人就知道，今天如果有八個設備點開，就會有八個子視窗，這使切視窗的操作變得難一些，甚至需要去尋找目前要設定設備是哪個子視窗。
原本搭配 GNS3 的 Solar-Putty 是預期可以發揮這項功能，但是我在第二分頁時，就會跳出「Putty」的子視窗，這沒起到分頁式的效果。但經簡單測試，改GNS3的參數是宣告無效的，如果手動在cmd輸入指令就可以是分頁式，與其這樣，倒不如換一個軟體。
Super-Putty 是以 Putty為底的，免費且開源的軟體，可以用在商業與非商業用途。

如果要在GNS3使用Super-Putty的話，就以下的步驟進行。
STEP1：下載，至官方網頁下載「Download SuperPuTTY-1.4.0.9.zip」，然後解壓縮。
STEP2︰壓縮完後，進去找到「SuperPutty.exe」，右鍵內容，把完整位置複製
STEP3：在GNS3按下「Ctrl + Shift + P」，並切到「Console applications」
STEP4：在GNS3按下「Ctrl + Shift + P」，並切到「Console applications」，按下「Edit」
STEP5：切換到「SuperPutty」
STEP6：切換到「SuperPutty」，把完整位置加上前後雙引號貼上。
STEP7：回到GNS3，開啟「Console」。
STEP8：第一次執行Super-Putty，會需要設定Option，要指定putty.exe的位置，而putty.exe在GNS3的資料夾中。
STEP9：切到「Advance」，勾選「Only allow single instance of SuperPuTTY to run」

STEP10：開啟兩設備的console，可以看到SuperPuTTY以分頁的型式呈現各設備的連線。

2020-06-22 最近暫停寫Leetcode題解

感覺要有一個可以碎碎念的地方，所以就有了這一篇。最近要準備的有點多，所以決定先暫停Leetcode題解，把時間挪給更優先的事情。

現在經營有兩大主軸︰「Leetcode題解」跟「JN的CCNA」。
手一捏，可能會停二個月，不過關於「網路」的是不會停，因為那是目前最優先的部分。
而「JN的CCNA」在準備中，等到完成 25% 就會上線，我也不喜歡看到了一堆章節，但裡面卻沒有任何內容。QQ
總之就是這樣，如果有要回來一直寫，就會再公佈。目前只會有零星的手癢來寫題解。

人生第一次面試

今天是第一次面試，有人說第一次面試一定會搞糟，嗯，感覺真的搞糟，所以面試完心裡有底了。但也感謝這場面試讓我知道哪裡不足，下次可以改進。
自己在面試上還有很多可進步的地方，讓我了解自己的不足，最近接踵而來的面試邀約，也不知道有辦法可以短時間內就完成改進。還是一句「best effort」。
雖然是第一次面試，但我倒是不緊張，畢竟也不知道會問什麼。過程中令我最難應付的是：解釋「網路」，網路是個很大的領域，如果是科普的，那不是問題。但如果是要講給對網路有很好了解的人，面試官，那要講什麼才能反映當前的水準，如果講太淺，又顯得很普通。

我沒有想過要如何對於有程度或程度遠超過我之上的人要講什麼才能獲得青睞，所以就拿家用路由器最近遇到的問題來說。我覺得很糟，自認為這個題材選擇不好。面試前我預期會問一些CCNA、範圍比較明確的，我應該不會答太差。不過我也覺得要想想如何把網路講得有程度，目前想法就把一張生活圖畫出來，來把各部分簡單帶過，也許會花半小時吧，自認為可以講一小時都沒問題，講到面試官喊停為止。
回到，我這次講的家用路由器問題時，我也沒有答很明確，但其實面試官想聽的沒有我想的那麼難。
我推論是問題出在於內部，因為對外路由器能ping通外部，但電腦無法，只能通到對外路由器。我的想法是dhcp出了問題，ip 位置可能重疊到， 因為dhcp發送範圍有包含電腦自設的靜態位置。重新啟動家內的路由器跟修改Ip位置（不要在dhcp的範圍）就能解決。
當下其實我想到「arp」去查，但是不是在電腦端用「arp」，而是要在中間的路由器上，不過路由器是GUI模式，就不能直接能輸入 arp 去查，所以就沒有回答。最後也只能講用ping，結果面試官也這樣認同。不過ping能查的未必是ip重疊的情況，沒有直接影響。
面試官說IP重疊只要接一個Switch在中間就能查，這是基本，我也這麼覺得。
不過家用環境不會多一顆Switch，雖然其實大部分的家用router是多功能的，也能變成layer3 switch，但也不會有一台多的。以我的偏好來說，不改變topology 的情況下，能查出來是最好的。所以這種方法，可行，但不是最佳解。
照我的推論，應該要用「arp -a」或是「dhcp binding」查是否為這個問題。
沒提到的是，以前也常發生這樣的問題，只要電源拔插就能解決。但是沒有真的把問題找出來過，這是我的不足。
更大的敗點是我沒有補充得更多細節，也許畢竟CCNA還太菜，自從我看到NP就知道還有很多進步空間，但不代表NA不能參與網路問題的討論，如果有想法，也可以分享，不然會被覺得沒學好。如果碰到這樣的問題，就主動跟面試官分享自己的看法，同時這樣的人，也比較是公司想要的人，下次我有這樣的時我應該多說一些自己的看法。
這次面試走誠實流，誠實必然會有一些弱點，但不會心虛，這是第一次也不用太斤斤計較因為，有了第一次，才能在後面有更好的應對。面試主要是給印象，要讓人真心覺得你就是這樣人，如果有吹噓，那可能會被明眼識破。誠實流也蠻對我的味，下次面試會改進一些說法，讓一些經歷有更好的解釋。
最後，也感謝這場面試讓我知道哪裡不足，下次可以改進。

GNS3安裝與設定教學(2.2.10) ※疑難：GNS3無法順利連上VM。(VMware Player)

今天要來把GNS3的一步一步安裝完成，因為安裝設定是對於網路初學者是有一點困難，這裡以「沒有經驗」的為對象，如果有經驗了，也不一定要照做。

官方的安裝教學(Windows)，如果不排斥看英文，個人認為這裡更好。

第一步：下載 GNS3

上GNS3官網，點 Download，然後會要求要有GNS3的帳號。註冊後，就能下載。
下載 GNS3

第二步：安裝 GNS3

一路按「Next」或「I Agree」
如果沒有VM檔的可以勾選，可以先把VM檔下載回來，但一般不用勾。
至於Tools，新手全勾選，有些是必須安裝才能順利使用。
官方對於Tools的簡短敘述
選一個VM Type的VM檔
(個人建議選 VMware Workstation)
VMware跟VirtualBox蠻大型就不在這裡多介紹，Hyper-V是Windows10的才有的，而且在職缺來說，使用Hyper-V的也有不少數。
一路往下跑安裝，「Solar-PuTTY」會要填Email的，填一下，因為之後GNS3會預設使用，到時還是得填才能使用，不然就要改設定。

第三步：設定 GNS3

首次進入GNS3，會看到這個畫面。
沒有特別需求就按「Next >」
下一步會做一些GNS3 VM的設定，此時選 VMware。如果是純新手，這個時候需要把VM Software，給安裝完成，而且 GNS3 VM的VM檔還沒有匯入到 VM Software。最後，VM Software 裡面要有「GNS3 VM」才能順利執行。
不同的VM Software會對應不同的VM檔，如果安裝中沒有下載的，VM檔可以到官方下載。
需要先在VM Software匯入VM檔才能下一步
※CPU數跟記憶體預設為 1、2048MB，VM檔預設也是如此，二者建議相同。
若第一次用就不去改參數，因為用預設下，二者也會一致。

如果是新手，而且又用「VMware Workstation Player」的，接下來是

「十分重要」

除了「WMware Wokstation Player」還需要「VMware VIX」才能讓GNS3順利執行VMware的GNS3 VM。
VMware VIX需要「1.17」版，連結，如果頁面被跳轉，用搜尋也可在第二頁看到。

WMware Wokstation Player需要「14」版，連結，用15版會不能順利執行。

安裝二者後，打開WMware，去匯入VM檔。(圖為15版，但14版也一樣。)
先打開VM Software，這裡以「VMware」為例。
然後把剛下載的VM檔ZIP解壓縮後匯入VM檔。
如果第一次沒有設定好，之後可以在這裡設定。
如果有順利設定好，GNS3 VM要亮綠燈。
而且，在每次開GNS3時，都會自動用VMware打開VM。
最後要測試VM是否能連上Internet，如果可以，後面就能專注要模擬練習的部分。先參考「GNS3模擬器」的「如何找到GNS3適合的Router與Switch」，加入一些可用的設備後，就可以開始使用GNS3做模擬設備練習。
VM進入「Test」測試，就可以知道VM是否能上網。

疑難雜症區

GNS3無法順利連上VM。(VMware Player)

22020-06-23，不知道是昨日Windows更新的問題，今天用GNS3無法連到VM，然後跳出一個訊息：
「Error while getting the VMs: The server vm is not a GNS3 server or it’s a 1.X server」
意思很簡單，就是目前的VM被認為不是GNS3 VM。
打開GNS3可以順利啟動VM，那最簡單的方法是重載一次VM，重設定，這樣就完成了第一步驟。
對於「VMware」來說，必須先在GNS3內去跟VMware產生的Host介面(VMnet1)連結，才能順利跟VMware產的VM做連結。
如果是用DHCP的，經過這一步驟也能讓VMware 虛擬 Host 介面跟VM做連結，然後介面會取得一個以DHCP方式得到IP位置，接下來用電腦就能ping到VM就能通。
作者用過「Vitual Box」跟「VMware」目前只在VMware發現需要有這個步驟。

打開GNS3，GNS3也順利執行VM，但發現VM不通
拖曳 Cloud 跟  VPCS (在 local server) 
對 Cloud 按右鍵點 Console
勾選「Show special Ethernet interfaces」
然後上方切到「VMware Network Adapter WMnet1」
點「Add」
按下OK後，把 PC1 跟 Cloud 的 VMnet1 接起來。
啟動PC1，然後進入Console
這時用「CMD」打「ipconfig」去查「VMnet1」的位置
參考並選一個IP位置要做為PC1的IP位置。
(不知道的可以拿尾碼加1，此例為10.1.1.4)
設定IP位置，並
嘗試Ping VMnet1(位置在ipconfig可查)
嘗試Ping VM(寫在VM的資訊頁)
檢查GNS3 VM是不有亮綠燈
沒有則重啟GNS3，再看是否有沒有亮綠燈

Leetcode題解 Python & C#六月挑戰DAY20 Permutation Sequence

給一個數字 n  代表有 [1,n] 個數字要排列組合，k 代表要找第 k 小的，找出後回傳。
這題一看到時，我想起姊妹題的排列組合找下一個，使用兩兩交換，但這題不是。
這題的限制條件使n最多只有9個，也不重複，因此，使這題可以用規律性去找解法。
如：123 一共有六種組合。
123
132
213
231
312
321

當 k == 3 的時候，第一個數字為2，因為每一個首位數的後面只有2種組合，因些每個首位數字只佔2個，
所以透過除以區間數，就能以商去判斷當前是哪一個數字。
完成了第一步，後面下一個數字能用同樣的模式接上就能解出來了。
如果 k == 3 ，也取了第一個數字 2，剩下的 [1,3] ，可以用分治法的想法去看成子問題︰[1,3] 和 k2 的要找當前數字是什麼。
k2 是多少？因為是 k = 3 所以我們可以預期第二個數字是 1，拿 k2 去除區間大小(1)，得到的商應該是 0 才對，代表從[1,3]取位置[0]出來。
這時有一個問題，是商去決定當前是哪個數，那 k2 應該要是 0 ， 因為 0 除以 1 才會為 0，但 k / 2 = 1…1 ，餘數 1 並沒有對上 k2 去。
為什麼？因為位置系統是以 0 為首，但第 k 小是以 1 為首，所以對不上，因此只要把 k – 1 就能使位置對齊。 
最後，只剩一個要取的數時，後面也沒有組合數了，不能再跑下一個迴圈，就直接把最後一個未取的數補到最後方即可。

Python 

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        result = ""
        nums = [str(i) for i in range(1, n+1)]        
        method = [1]
        for i in range(1, n):
            method.append(method[i-1]*i)
        k -= 1
        for i in range(n-1, 0, -1):
            result += nums.pop(k // method[i])
            k = k % method[i]
        result += nums.pop()        
        return result

C# 

public class Solution {
    public string GetPermutation(int n, int k) {
        var result = new List();
        var number = new List();
        var factorial = new int[9];
        factorial[0] = 1;
        for(int i = 1; i < n; i ++)
        {
            factorial[i] = factorial[i-1]*i;
            number.Add(i);
        }
        number.Add(n);        
        k -= 1; 
        for(int i = n-1; i > 0; i--)
        {            
            result.Add(number[k / factorial[i]]);
            number.RemoveAt(k / factorial[i]);
            k = k % factorial[i];  
        }         
        result.Add(number[0]);
        return string.Join("", result);
    }
}

Leetcode題解 Python：六月挑戰DAY19 Longest Duplicate Substring

給一字串 S，要找出最大的重複連續字串，重複字串可部分重壘。
參考︰力扣 
在這題出的這天，感覺最近要開始爆忙，也在想要不要先斷一下寫題解？但這題有難度，還是想把它做掉。
這題要用到「Rabin-Karp ‘s algorithm」，用來字串搜查，使用方法是把子字串做Hash轉換去對比。
但我從頭開始講，為什麼得用 Rabin-Karp ‘s algorithm ？
要從一字串內找的重複出現子字串時，會使用 suffix Array，中文是後綴表。

suffix Array
例一：
banana，生成後綴表 => [banana, anana, nana, ana, na, a]
然後依字母大小跟長度排序 => [a, ana, anana, na, nana, banana]
拿 [i] [i+1] 去找前綴最長共同長度 => a,ana: 1, ana,anana:3 ,…
共同前綴最長部分就是題目所求，也就是取最大值。
為什麼可行？在排序的時候，就已經把性質相近，組成相似的排在一起，因此只會跟最有可能有最長共同前綴的相比。
這方法的時間複雜度很大，因此需要改良。
提示一：Binary Search。
例二：
banana 的長度為 6，因此最大重複字串的長度不會超過五，會落在[0,5]間，從中間先找長度 3 有沒有出現重複子字串，
這會比起例一每次都從長度 1 開始，還快上不少。
比較的參照是用 HashSet，取二分法的長度 m，從頭把長度 m 的子字串輪一遍，先檢查是否在 HashSet，若有就是有重複出現，沒有就把放入HashSet。  
因此 banana 會從長度 3 開始，有，l = 4。接著 m = (6-4)//2+4 = 5，拿長度 5 找，沒有，r = 5。
最後 m = 4，沒有，r = 4，此時 l 3。
找到重複時，就可以回傳其對應到的位置，也不用繼續找 下去。
但是，數量一大，子字串是 string，長度相對也會爆炸式增長，這使得記憶體會巨大消耗，會超使用限制。
提示二：Rabin-Karp ‘s algorithm。
用簡單來講，就是把字串的位置跟值做 hash，然後得到一個能表示字串組合的hash值，該值若有在HashSet，就代表有重複。
把可能出現的值給一個對應值，這題只有英文小寫字母，故會有26個值，從 0 到 25 。
如果長度為2為下，hash值為0，那可對應 aa。hash值26，為ba。
例二的最大問題是「記憶體使用太多」，如果把子字串資訊轉換成hash值，hash值不超過 log2(26*26)，
也就是佔用不超過10bit，但長度為2的string，至少也16bit。因此可以有效解決記憶體使用太多的問題。
雖然目前的hash值保證為1對1，但如果這樣算，一旦長度為32以上，hash值可能有超過26**32，這值太大會在某些語言造成溢位出現。
把值對一個大數取餘，就能限制hash值的長度，也會有開始有多值對一個hash的可能，但大數夠大，發生的機率是相當的低。(大部分的hash都會去限制長度，如：MD5、SHA256)
我不是很喜歡這題，因為正確的寫法可能會過不了。

Python 

class Solution:
    def longestDupSubstring(self, S: str) -> str:        
        hashMap = dict()
        count = 0
        nums = []
        for c in S:
            if c not in hashMap:
                hashMap[c] = count
                count += 1
            nums.append(hashMap[c])
            
        mod = 2**64
        def search(length):            
            SubStrHash = 0            
            for i in range(length):
                SubStrHash = (SubStrHash*count + nums[i])%mod            
            hashset = {SubStrHash}
            al = (count**length)%mod
            for i in range(length, n):
                SubStrHash = (SubStrHash*count - nums[i-length]*al + nums[i])%mod
                if SubStrHash in hashset:
                    return i        
                hashset.add(SubStrHash)
            return -1                
            
        n = len(S)
        l, r = 0, n
        end = -1
        while r > l:
            m = (r - l)//2 + l
            res = search(m+1)
            if res == -1:
                r = m                 
            else:
                l = m + 1
                end = res
       
        return "" if end == -1 else S[end - r + 1: end+1]

目前趨勢

忘記行李後的心情低落
2017.9.23 學習了一個月的python歷程
臺鐵大誤點以及捲簾式快門
嘗試用Python爬蟲技巧抓混音音樂