2014-06-24

UVa 11837 - Musical Plagiarism

1. Problem
2. Input
3. Output
4. Sample Input
5. Sample Output
6. Solution

Problem

The musical notes are the basic units of Western music. Each note is associated with a frequency. Two notes for which the fundamental frequencies have a ratio of power of 2 (one is half of the other, one is double of the other, etc..) are perceived as very similar. Therefore, any notes with that kind of relationship are given the same name, as described below.

There are twelve basic notes in a sequence of increasing frequency, each note separated from the previous note by the same distance in the musical scale (this distance is called a semitone). Seven of these twelve notes are represented by letters of the alphabet (A, B, C, D, E, F and G). The table below shows the distance, in semitones, between the notes.

Notes A-B B-C C-D D-E E-F F-G G-A
Number of semitone 2 1 2 2 1 2 2

Notice that there are five notes that are not represented by letters of the alphabet: the notes between A and B, between C and D, between D and E, betwen F and G and between G and A.

Notes can be modified by two accidentals, called sharp and flat, represented respectively by the symbols #' andb’. A sharp raises the note a semitone, a flat lowers the note a semitone. A note with an accidental is denoted by the name of the note followed by the accidental symbol. Notice that with this scheme we can represent all twelve notes.

The figure below illustrates the name of the notes in accordance with the scheme described above, in a fragment of a piano keyboard.

A melody can be represented by a sequence of notes. For example,

A A D C# C# D E E E F# A D G# A

is a well known melody. Note however that as the distances between the semitones are always equal, the same melody can be written starting with another note (we say that the melody is in another key):

B B E D# D# E Gb Gb Gb G# B E A# B

Your neighbor is a famous composer who suspects someone has plagiarized one of her songs. She asked your help to write a program that, given the sequence of notes of the melody in her song, and the sequence of notes of a suspicious snippet of melody, determines if the suspicious snippet occurs, in some key, in her song.

Input

The input consists of several test cases. The first line of a test case contains two integers M and T ( 1$\le$M$\le$105, 1$\le$T$\le$104, T$\le$M), indicating the number of notes in the song suspected of having been plagiarized and in the suspect snippet. Each of the next two lines contains M and T notes, respectively, indicating the notes of the song and of the suspect snippet.

Notes in each line are separated by one space; each note is one among A',B’, C',D’, E',F’ or G', possibly followed by an accidental sign:#’ for sharp or `b’ for flat.

The last test case is followed by a line containing only two zeros separated by a blank space.

Output

For each test case your program must print a single line containing one character, S' in case the song has been plagiarized by the text, orN’ in case the song has not been plagiarized by the text.

Sample Input

16 4
D G A B C D G G G C D E F# G C C
G G C D
12 2
C C# D D# E F F# G G# A A# B
C D
12 2
C Db D Eb E F Gb G Ab A Bb B
C D
4 3
C E G Bb
D F# A
0 0

Sample Output

S
N
N
S

Solution

題目描述：

音階全全半全全全半，全音中間夾一個黑/白鍵，半音之間沒有。

計算是否為旋律中的一部分，計算旋律時只需考慮音符之間的距離即可，與高低幾度偏移沒有關係。

題目解法：

特別小心，查詢的旋律長度為 1 的時候，無法判斷 (雖然以子字串是有在的)。

接著，直接對距離之間取模之後得到兩個整數序列，直接套用 KMP 判斷序列是否在另一個序列中。

#include <stdio.h>
#include <algorithm>
using namespace std;
int notes[128] = {};
int kmpTable[500005];
void KMPtable(int *P, int len) {
    int i, j;
    kmpTable[0] = -1, i = 1, j = -1;
    while(i < len) {
        while(j >= 0 && P[j+1] != P[i])
            j = kmpTable[j];
        if(P[j+1] == P[i])
            j++;
        kmpTable[i++] = j;
    }
}
int KMPmatching(int T[], int P[], int tlen, int plen) {
    for(int i = 0, j = -1; i < tlen; i++) {
        while(j >= 0 && P[j+1] != T[i])
            j = kmpTable[j];
        if(P[j+1] == T[i])  j++;
        if(j == plen-1) {
            j = kmpTable[j];
            return i;
        }
    }
    return -1;
}
int main() {
    int M, T;
    int A[100005], B[10005];
    char s[10];
    notes['C'] = 0, notes['D'] = 2;
    notes['E'] = 4,	notes['F'] = 5;
    notes['G'] = 7,	notes['A'] = 9;
    notes['B'] = 11;
    while(scanf("%d %d", &M, &T) == 2 && M + T) {
        int prev, x;
        for(int i = 0; i < M; i++) {
            scanf("%s", &s);
            x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
            if(i)	A[i - 1] = (prev - x + 12)%12;
            prev = x;
        }
        for(int i = 0; i < T; i++) {
            scanf("%s", &s);
            x = (notes[s[0]] + (s[1] == '#') - (s[1] == 'b') + 12)%12;
            if(i)	B[i - 1] = (prev - x + 12)%12;
            prev = x;
        }
        KMPtable(A, M - 1);
        puts( KMPmatching(A, B, M - 1, T - 1) >= 0 ? "S" : "N");
    }
    return 0;
}

Morris' Blog