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


yes51851823@gmail.com (wseds)

學校 : 國立花蓮高級工業職業學校
編號 : 108813
來源 : [36.227.245.149]
最後登入時間 ：
2024-04-16 01:11:16
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 (一葉之秋)

學校 : 新北市立板橋高級中學
編號 : 68688
來源 : [1.172.131.82]
最後登入時間 ：
2024-01-11 01:11:14
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 (一葉之秋)

學校 : 新北市立板橋高級中學
編號 : 68688
來源 : [1.172.131.82]
最後登入時間 ：
2024-01-11 01:11:14
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)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 82069
來源 : [220.130.10.185]
最後登入時間 ：
2024-04-01 11:16:18
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)

學校 : 不指定學校
編號 : 68108
來源 : [1.168.27.172]
最後登入時間 ：
2024-04-24 20:07:19
f416. 果然我的期中程設考搞錯了什麼 | From: [61.223.46.134] | 發表日期 : 2020-11-15 12:57

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

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


DE45A (一葉之秋)

學校 : 新北市立板橋高級中學
編號 : 68688
來源 : [1.172.131.82]
最後登入時間 ：
2024-01-11 01:11:14
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)

學校 : 國立臺灣師範大學附屬高級中學
編號 : 82069
來源 : [220.130.10.185]
最後登入時間 ：
2024-04-01 11:16:18
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._______ __)

學校 : 不指定學校
編號 : 162320
來源 : [60.248.91.97]
最後登入時間 ：
2023-11-02 20:49:18
f416. 果然我的期中程設考搞錯了什麼 | From: [36.231.66.168] | 發表日期 : 2023-11-23 15:49

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

 

a="aaaaa"

b="aaaaaaaaaaaaaaaaaaaaaaaaaaaa"

 
ZeroJudge Forum