發表新討論
#23402: 只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


yes51851823@gmail.com (wseds)

f416. 果然我的期中程設考搞錯了什麼 | From: [111.243.226.228] | 發表日期: 2020-11-13 21:04

針對字串b中每個長度|a|的區段計算出每個字母共有幾個，只要有區間每個字母出現次數與a字串一樣，就掃看看a是否與該區段相等。

如此一來，複雜度為O(N×26)，掃到每個字母數相等區段時複雜度再加|a|。

#23403: Re:只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


DE45A (一葉之秋)

f416. 果然我的期中程設考搞錯了什麼 | From: [1.172.133.127] | 發表日期: 2020-11-13 21:59

針對字串b中每個長度|a|的區段計算出每個字母共有幾個，只要有區間每個字母出現次數與a字串一樣，就掃看看a是否與該區段相等。

如此一來，複雜度為O(N×26)，掃到每個字母數相等區段時複雜度再加|a|。


為什麼不直接寫KMP或Z value QQ

#23404: Re:只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


DE45A (一葉之秋)

f416. 果然我的期中程設考搞錯了什麼 | From: [1.172.133.127] | 發表日期: 2020-11-13 22:00

針對字串b中每個長度|a|的區段計算出每個字母共有幾個，只要有區間每個字母出現次數與a字串一樣，就掃看看a是否與該區段相等。

如此一來，複雜度為O(N×26)，掃到每個字母數相等區段時複雜度再加|a|。


不過我不會再改測資了 除非有錯

#23419: Re:只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


089487 (089487)

f416. 果然我的期中程設考搞錯了什麼 | From: [140.118.139.193] | 發表日期: 2020-11-15 12:01

針對字串b中每個長度|a|的區段計算出每個字母共有幾個，只要有區間每個字母出現次數與a字串一樣，就掃看看a是否與該區段相等。

如此一來，複雜度為O(N×26)，掃到每個字母數相等區段時複雜度再加|a|。


不過我不會再改測資了 除非有錯


可以請教這題和Z value的關係嗎?

這題不就只是KMP

#23420: Re:只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


asnewchien@gmail.com (david)

f416. 果然我的期中程設考搞錯了什麼 | From: [61.223.46.134] | 發表日期: 2020-11-15 12:57

發文還加時間戳... 哈～

#23421: Re:只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


DE45A (一葉之秋)

f416. 果然我的期中程設考搞錯了什麼 | From: [1.172.133.127] | 發表日期: 2020-11-15 15:34

針對字串b中每個長度|a|的區段計算出每個字母共有幾個，只要有區間每個字母出現次數與a字串一樣，就掃看看a是否與該區段相等。

如此一來，複雜度為O(N×26)，掃到每個字母數相等區段時複雜度再加|a|。


不過我不會再改測資了 除非有錯


可以請教這題和Z value的關係嗎?

這題不就只是KMP


Z value也可以做

用其中一個作的可以

#23588: Re:只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


089487 (089487)

f416. 果然我的期中程設考搞錯了什麼 | From: [223.137.185.156] | 發表日期: 2020-11-30 20:13

針對字串b中每個長度|a|的區段計算出每個字母共有幾個，只要有區間每個字母出現次數與a字串一樣，就掃看看a是否與該區段相等。

如此一來，複雜度為O(N×26)，掃到每個字母數相等區段時複雜度再加|a|。


不過我不會再改測資了 除非有錯


可以請教這題和Z value的關係嗎?

這題不就只是KMP


Z value也可以做

用其中一個作的可以


也可以用hash

#38444: Re: 只要測資沒再被改動 這應該是OK的演算法 （2020/11/13 21:00）


liaojoy985@gmail.com (yay._______ __)

f416. 果然我的期中程設考搞錯了什麼 | From: [36.231.66.168] | 發表日期: 2023-11-23 15:49

完全不OK，我隨便構都能構出讓這個O(|a||b|)的測資

 

a="aaaaa"

b="aaaaaaaaaaaaaaaaaaaaaaaaaaaa"

ZeroJudge Forum