盡量不要對(duì)自己的想法抱有什么期待，當(dāng)然主觀上的，感性的想法除外。

467. 環(huán)繞字符串中唯一的子字符串

把字符串?s?看作?"abcdefghijklmnopqrstuvwxyz"?的無限環(huán)繞字符串，所以?s?看起來是這樣的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd...."?。

現(xiàn)在給定另一個(gè)字符串?p?。返回?s?中?不同?的?p?的?非空子串?的數(shù)量?。?

其實(shí)我的想法和官方的想法，在基礎(chǔ)的部分是對(duì)上了的，比如確定一個(gè)起點(diǎn)（終點(diǎn)）和長(zhǎng)度就能夠確定一個(gè)子串。但在有了基礎(chǔ)的認(rèn)識(shí)以后，我的思路就開始往復(fù)雜的方向偏離了。

我驚人的發(fā)現(xiàn)了一個(gè)規(guī)律，一個(gè)字符串的子串?dāng)?shù)量，是滿足n*(n+1)/2這個(gè)通項(xiàng)公式的。比如abcd，它的長(zhǎng)度是4，4x5%2=10，所以abcd的子串的數(shù)量是10(包含自己)。

順著這個(gè)思路，我想著把所有的子串的數(shù)量都算出來，再減去重合的部分就完事了。

然后問題的重心就來到了怎么算重合部分，其實(shí)到這里我已經(jīng)走偏了，但我還是想順著自己的思路來，畢竟如果這是考試或者真正的問題，我肯定還是會(huì)這么做。

此時(shí)問題變得復(fù)雜了，子串的重合有整整四種情況。但好在浪費(fèi)了很多時(shí)間我還是想出來了。

但是有了新的問題，子串b如果和子串a(chǎn)重合，減去這個(gè)重合部分，此時(shí)子串c和ab都有重合部分的話，就會(huì)多減一次。于是我記錄了每個(gè)子串已有的重合，如果多減了就把多減去的部分再加回來。

到這里我還沒意識(shí)到不對(duì)，此時(shí)新的問題又出現(xiàn)了：加上多減的部分的邏輯是有漏洞的，簡(jiǎn)單說就是某些情況下會(huì)多加，于是我又需要新的邏輯和多余的變量來處理這個(gè)問題......

到這里我差不多沒轍了，我沒法保證浪費(fèi)那么多腦力想出的辦法解決了這個(gè)問題，程序就能正常運(yùn)行，而且就算能，效率也是肉眼可見的低，大概還是會(huì)超時(shí)。

我想了一下，歸根結(jié)底我還是在用軟件開發(fā)的思路去做算法題，首先確定要實(shí)現(xiàn)的功能，然后尋找實(shí)現(xiàn)的方法，實(shí)現(xiàn)以后再看一下有沒有什么不足，慢慢迭代。

軟件的功能無非就是調(diào)一下API，基本的思路不可能出錯(cuò)，但做題很可能從一開始就饒了遠(yuǎn)路。

官方題解又是動(dòng)態(tài)規(guī)劃，我又栽到了DP上，一開始就想過是不是可以DP，但是一看字符串最長(zhǎng)50000，馬上放棄了這個(gè)想法。簡(jiǎn)而言之還是和上次一樣，理解不夠，思路太死。

試著理解一下官方的想法：

核心的要點(diǎn)是：

1. 每個(gè)子串的結(jié)尾一定是26個(gè)字母中的一個(gè)。

2. 結(jié)尾相同的子串，長(zhǎng)度大的一定包含長(zhǎng)度小的。

根據(jù)1和2可以想到3：

3. p的每一個(gè)子串，甚至子串的子串，都可以表示成結(jié)尾字符+長(zhǎng)度的形式。

然后可以想到，只取某個(gè)字符結(jié)尾的子串的最大值，把26字符結(jié)尾的子串的長(zhǎng)度相加，就是全部的組合數(shù)，因?yàn)槿×俗畲笾邓员苊饬酥貜?fù)的問題，即使一個(gè)子串長(zhǎng)度超過26依舊滿足上面的三點(diǎn)。

我還是學(xué)不會(huì)，官方題解總能一眼看到問題的本質(zhì)，解法優(yōu)雅的離譜。多少有腦筋急轉(zhuǎn)彎的感覺，但是又不一樣，總覺得應(yīng)該是可以想出來的，可以依靠邏輯推出這個(gè)解法的。

簡(jiǎn)而言之，我還是傻逼，哪怕像它們一樣滿口高并低延大概率還是碼農(nóng)，只是調(diào)一下API傻逼也能做到，沒什么好吹的。難的是解決未知問題的能力，這是一切的基礎(chǔ)。