読者です 読者をやめる 読者になる 読者になる

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;
}