UVa11837 Music Plagiarism
問題文
http://uva.onlinejudge.org/external/118/11837.html
概要
鍵盤が同じ間隔で打たれているとき、譜面Bは譜面Aのメロディを剽窃した疑いがある。疑いがある場合は 'S' そうでない場合は 'N' を出力せよ。(詳しい内容は本文参照)
解法
入力の表を配列に持ち、鍵盤の並びの差分を string A, B に記録する。あとは、A.c_str() の中から B.c_str() を strstr() で見つける。string の find() でもTLEとはならない。
以下の掲示板の書き込みによると、strstr() は 普通のKMPの実装並かそれ以上に速い?みたいなことが書いてある(と思う)。
参考資料
"strstr faster than algorithms?" - Stack Overflow
http://stackoverflow.com/questions/7586990/strstr-faster-than-algorithms
#include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0; i<(n); i++) #define SIZE (7) int semitones[SIZE] = {0, 2, 3, 5, 7, 8, 10}; int M, T; map<string, ll> mp; string input(int const N) { vector<string> vec(N); string ret; ret.resize(N-1); rep(i, N) cin >> vec[i]; rep(i, N-1) ret[i] = (char)((mp[vec[i+1]] - mp[vec[i]] + 12) % 12 + 'K'); return ret; } void init() { rep(i, SIZE) { mp[string(1, 'A'+i)] = semitones[i]; mp[string(1, 'A'+i)+'b'] = semitones[i]-1; mp[string(1, 'A'+i)+'#'] = semitones[i]+1; } } int main() { init(); for(;cin >> M >> T && M;) { string A = input(M); string B = input(T); if(strstr(A.c_str(), B.c_str()) != NULL) { puts("S"); } else { puts("N"); } } return 0; }