的子字符串的長度可以爲1,2,3 ...... ,我試圖解決涉及發現,發生的最大次數的子問題。所以它基本上打破了尋找具有最高頻率的角色。 但是,我發現我可以使用O(n)中的後綴樹找到最長的重複子字符串。 但是,後綴樹返回保持長度作爲優先級的子字符串。 我想找到發生次數最多的子字符串,並且希望找到最長的子字符串。 對於如:最長最大重複子
In the following string: ABCZLMNABCZLMNABC
A suffix tree will return ABCZLMN as the longest repeating substring.
However, what I am looking for is ABC; as it is the longest out of all the ones having frequency = 3.
我試圖用兩個指數i和j之間產生子解決這個問題。之後,使用在O(n)中運行的Z算法在每種情況下找到這些子串的出現。然而,總複雜度爲O(n^3)
我爲O(n^3)代碼
map<ll,vector<string>> m;
string s; cin >> s;
for(ll i=0;i<s.length();i++){
string c;
for(ll len=0; i+len<s.length();len++){
c+=s[i+len];
ll z[N];
ll l=0,r=0;
string kk;
for(ll p=0;p<c.length();p++){
kk+=c[p];
}
kk+="#";
for(ll p=0;p<s.length();p++){
kk+=s[p];
}
for(ll k=1;k<kk.length();k++){
if(k>r){
l=r=k;
while(r<c.length()&&kk[r-l]==kk[r])r++;
z[k]=r-l;
r--;
}
else{
ll m=k-l;
if(z[m]<r-k+l)z[k]=z[m];
else{
l=k;
while(r<c.length()&&kk[r-l]==kk[r])r++;
z[k]=r-l;
r--;
}
}
}
ll occ=0;
for(ll n=0;n<kk.length();n++){
if(z[n]==c.length())occ++;
}
m[occ].push_back(c);
}
}
我無法找到一個合適的解決方案,使之高效。 請幫忙。 謝謝。
嘿... homeworks? SO不是「爲我做」的網站。嘗試編寫一些代碼,並返回出錯的地方。 – folibis
好的,但至少要顯示你的代碼。 – folibis
我試着通過在兩個索引i和j之間生成子串來解決這個問題。之後,使用在O(n)中運行的Z算法在每種情況下找到這些子串的出現。然而總的複雜性是O(n^3)。 –