四邊形不等式

求解所有≤n數(shù)字中有多少個1？

我們的策略是劃分為兩部分:以最高位數(shù)字為1領頭的數(shù)字的個數(shù)+忽略最高位數(shù)字統(tǒng)計的1的個數(shù)。

例如123456789

1.最高位為億，所以以最高位數(shù)字為1領頭的數(shù)字為100000000——123456789，有（123456789－100000000+1）個

2.現(xiàn)在忽略最高位，但是要記住最高位數(shù)字為1，然后直接求0——99999999這上面出現(xiàn)了多少個1。

最終答案ans=1x（0——99999999的1的個數(shù)）+第一步求出的數(shù)據(jù)，即為原問題的答案。

那如何求0——99999999上1的個數(shù)呢？

不妨先求1000——9999上1的個數(shù)。首先以最高位1開頭的數(shù)字——(1000——1999)有1000個。然后統(tǒng)計忽略最高位的數(shù)字開頭的統(tǒng)計1的個數(shù)——9x(0——999上1的個數(shù)），先不要罵我，解釋，統(tǒng)計完最高位1開頭的數(shù)字后，剩下（1000——1999）（2000——2999）（3000——3999）（4000——4999）、（5000——5999）、（6000——6999）(7000——7999）、（8000——8999）、（9000——9999）9項，這9項都是忽略啦最高位為1的統(tǒng)計個數(shù)。由此1000——9999上1的個數(shù)統(tǒng)計完了。

現(xiàn)在我們從0——9開始，0——9上面有1個1；（10——99）上面有10+9x（0——9上1的個數(shù)）即使19個1；（100——999）上有100+9x[（0——9上1的個數(shù)）+（10——99上1的個數(shù)）]=100+9x（0－99上1的個數(shù)）……如果求（0——999）上1個數(shù)=（0——9）+（10——99）+（100——999）如此問題解決

后綴樹解釋:

1.由于1——4、2——5、3——6都一一對應了，所以沒辦法只能繼續(xù)讓123后面的456……和456后面的789……進行比較

2.而在表中456恰好比789排名靠后，所以這也預示了123企圖靠后面的456……排名超過456后面的789……的計劃打破了。所以沒有辦法，123排名靠后，456排名靠前

對于直接連接頭節(jié)點的節(jié)點來說，直接連接頭節(jié)點沒什么好說的！

對于普通節(jié)點

1.先看自己父親的file指針指向的那個節(jié)點，看那個節(jié)點有沒有指向自己這個字符的路，有就將自己的file指針指向它。

2.沒有的話，先來到自己父親節(jié)點file指針指向的位置，從這里開始一直順著file指針審查每一個節(jié)點，當?shù)谝淮斡龅街赶蜃约哼@個字母的節(jié)點停止，讓自己的file指針指向這個節(jié)點對應自己字母的路徑上的節(jié)點。

3.若一直沿著file指針向上到達了頭節(jié)點無路可走啦，就再從頭節(jié)點開始，看頭節(jié)點直接相連的next節(jié)點有沒有和自己字母一樣的，令自己的file指針指向那個字母所在位置。 若連頭節(jié)點直接的next指針都沒有和自己一樣的字母，沒辦法，只好讓自己指向頭節(jié)點。

意義:哪一個字符串和我當前經(jīng)歷的字符串的后綴相等且最長。比如有字符串a(chǎn)bcdefg、cdefg、efg。目前審查abcdefg，審查到了g位置，有兩個字符串和它一直匹配到目前的g位置。而我們的要求是:①要匹配到字符串當前的位置②不僅要匹配到當前字符位置，還要求不能和當前審查的這個字符串的開頭相同——不能與abcdefg的開頭的a也匹配啦，所以截止到g位置，理論上最長可以匹配bcdefg，發(fā)現(xiàn)沒有，縮小一下cdefg，這個有，成為最佳匹配！

總結(jié)匹配要求:

例1.匹配asdfghj……這個字符串。當前要找到j這個位置處的file指針進行asdfghj的匹配。但是要求對它進行匹配的這個字符串開頭不能和它一樣——也是a，那么理論上最多可以匹配到最長答案為sdfghj，實際上只能盡可能匹配。

例2.對于abcd、cd、d來說，目前匹配到了abcd中的d，我們可以匹配以d為結(jié)尾的bcd、cd、d，其中在其余字符串中有的最長的是cd。

為什么第一層file指針都指向頭節(jié)點？

因為身在第一層說明必然每個字符不相同，每個字符的file指針找不到和自己相同的字母，只好指向頭節(jié)點？

哪個字符串是完全等于以第一層為結(jié)尾的后綴整體的，只能是第一層這個節(jié)點本身，但是自己必然等于自己這沒有意義！

匹配文章的意義？

每一次盡可能的在一個單詞串上匹配，實在匹配不下去了跳轉(zhuǎn)到下一個地方承繼上面匹配的結(jié)果繼續(xù)匹配。