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


yes51851823@gmail.com (wseds)

學校 : 國立花蓮高級工業職業學校
編號 : 108813
來源 : [114.36.253.126]
最後登入時間 ：
2025-08-25 16:32:53
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.91]
最後登入時間 ：
2024-10-12 13:01:19
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.91]
最後登入時間 ：
2024-10-12 13:01:19
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
來源 : [140.112.16.132]
最後登入時間 ：
2025-04-29 20:27:54
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
來源 : [114.42.176.221]
最後登入時間 ：
2025-10-04 22:52:03
f416. 果然我的期中程設考搞錯了什麼
| From: [61.223.46.134] | 發表日期: 2020-11-15 12:57

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

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


DE45A (一葉之秋)

學校 : 新北市立板橋高級中學
編號 : 68688
來源 : [1.172.131.91]
最後登入時間 ：
2024-10-12 13:01:19
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
來源 : [140.112.16.132]
最後登入時間 ：
2025-04-29 20:27:54
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