Description

FST 是一名可憐的 ACMer，他很強，但是經(jīng)常 fst，所以 rating 一直低迷。 但是重點在于，他真的很強!他發(fā)明了一種奇特的加密方式，這種加密方式只有 ACMer 才能破解。 這種加密方式是這樣的:對于一個 01 串，他會構(gòu)造另一個 01 串，使得原串是在新串 中沒有出現(xiàn)過的最短的串。 現(xiàn)在 FST 已經(jīng)加密好了一個串，但是他的加密方式有些 BUG，導致沒出現(xiàn)過的最短的 串不止一個，他感覺非常懊惱，所以他希望計算出沒出現(xiàn)過的最短的串的長度。

Input

單組數(shù)據(jù) 一行，一個 01 串，字符串串長小于等于10^?5

Output

一行，一個正整數(shù)，表示沒有出現(xiàn)過的最短串的長度

Sample Input

100010110011101

Sample Output

4

題意：在一個很長的串內(nèi)找到一個沒有出現(xiàn)過最短的子串，由于串比較長，所以我們不能直接對于字符串進行處理。我們可以換一個思想，從答案的長度入手，每次枚舉答案的長度，然后把這個很長的子串拆分很多這個長度的子串，
放到set當中存儲，利用set的去重，如果最后的set的size()<2^（ans）也就是小于我們枚舉長度能產(chǎn)生所有的可能的串的數(shù)量，那么就說明當中肯定有一個串沒有出現(xiàn)過。
就可以得到答案。

這題也可以用字符串hash去做，時間復雜度會比set+string的要小些。但是思想是一樣的。 #include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> #include <set> using namespace std;string s; set<string>ss; int main() {cin>>s;int len=s.length();string temp="";int ans=1;while(1){ss.clear();for(int i=0;i<=len-ans;i++){ // cout<<i<<endl;for(int j=i;j<i+ans;j++){temp+=s[j];} // cout<<temp<<endl;ss.insert(temp);temp="";} // cout<<ss.size()<<endl;if(ss.size()<pow(2,ans))break;elseans++;}printf("%d\n",ans);return 0; }/**********************************************************************Problem: 2188User: therangLanguage: C++Result: ACTime:540 msMemory:3580 kb **********************************************************************/

　　

轉(zhuǎn)載于:https://www.cnblogs.com/jkzr/p/9956613.html

總結(jié)

以上是生活随笔為你收集整理的CSU2188: Substring的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。