[問題] 兩數列的比較

[Arton0306 (Ar藤)]

小弟不知道這問題是否有名字

問題如下
一長數列長度m 如
3 5 4 2 1 4 3 5 1
一短數列長度n 如
3 4 5

求 短數列對應到長數列的哪片段 會有最小的euclidean distance

像這個例子 會對到
3 5 4 2 1 4 3 5 1
3 4 5
          3 4 5

數字範圍0~100的整數
100000>m>1000 10000>n>10
m>n

想問是否有比O(mn)更好的算法??

感謝!!

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.229.83
推 DJWS:dynamic time wraping
→ Arton0306:DTW是可拉長縮短的
→ Arton0306:我的是pattern多長 對到的就多長 不用做長度變化
※ 編輯: Arton0306       來自: 140.114.229.83       (09/06 00:52)
※ 編輯: Arton0306       來自: 140.114.229.83       (09/06 00:53)
→ Arton0306:這樣一樣是往dtw的方向查嗎
推 DJWS:抱歉我沒有搞清楚 XD 不過他們應該都算是sequence alignment
→ Arton0306:OK 謝謝
推 LinkCar:開101個stack 分別對應0~101
→ LinkCar:讀到片段中的數字 再丟入編號為該數字的stack
→ LinkCar:丟入新讀到的片段數字  丟掉過時的片段末數字
→ LinkCar:判斷101個stack與n個數字的異同    101*m  ->   O(m)
推 yoco315:樓上的能不能回一篇完整一點的 @@" 這樣我看不是很懂
→ yoco315:麻煩了，多謝...
→ AmosYang:LinkCar 的解法在 "找對應到的數列" 這部分是 O(m)
→ AmosYang:但若還要計算 euclidean distance, 我想 O(mn) 還是跑不
→ AmosYang:掉 XD (除非文中所述的的 euclidean distance 跟我所想
→ AmosYang:的是不一樣的東西…) :p
推 AmosYang:yoco315, LinkCar 大概是筆誤; 你把 "stack" 換成
→ AmosYang:"int array" 大概就能看懂了
推 LinkCar:對 只是個counter而已  而且也不一定是101 題目剛好
推 LinkCar:請問題目中的euclidean distance為何意思??
→ LinkCar:查完資料了解了，是我沒弄懂原本題意