UVA11837 Musical Plagiarism

lcyxds · 2024-11-17 20:30:25 · 题解

前置知识：乐理（音程），差分，剩余系，字符串匹配（KMP）

不妨使用 A 以上的半音数来代表音高，例如 A\sharp=1,D\flat=4 等。此时自然小调音阶 ABCDEFG 可以被表示为 0,2,3,5,7,8,10（可以通过图片或者表格处理出来）。以这个规则将旋律转换为数组。

两个旋律相似当且仅当构成的音程相同（或差八度），而音程在旋律数组中体现为差分。为了消除八度影响，将差分数组模 12 即可。

最后判断动机差分是否是旋律差分的子串，可以用 KMP 实现。

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <iomanip>

#define ll long long

using namespace std;

const int MOD = 12;

const int MINOR_SCALE[] = {
    0, 2, 3, 5, 7, 8, 10
};

int Sharp(int a) {
    return a + 1;
}

int Flat(int a) {
    if (a) {
        return a - 1;
    }
    return 11;
}

int ReadNote() {
    string s;
    cin >> s;
    int note = MINOR_SCALE[s[0] - 'A'];
    if (s.length() == 1) {
        return note;
    }
    if (s[1] == '#') {
        return Sharp(note);
    }
    return Flat(note);
}

int Sub(int a, int b) {
    int res = a - b;
    if (res < 0) {
        return res + MOD;
    }
    return res;
}

int n;
int m;
vector<int> s;
vector<int> t;
vector<int> kmp;

void ReadList(vector<int>& a, int len) {
    a.resize(len - 1);
    if (len > 1) {
        int last = ReadNote();
        for (int i = 0; i < len - 1; i++) {
            int nxt = ReadNote();
            a[i] = Sub(nxt, last);
            last = nxt;
        }
    }
}

void Kmp() {
    kmp.resize(m);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j && t[i] != t[j]) {
            j = kmp[j - 1];
        }
        if (t[i] == t[j]) {
            j++;
        }
        kmp[i] = j;
    }
}

bool Match() {
    int j = 0;
    for (int i = 0; i < n; i++) {
        while (j && s[i] != t[j]) {
            j = kmp[j - 1];
        }
        if (s[i] == t[j]) {
            j++;
            if (j == m) {
                return true;
            }
        }
    }
    return false;
}

bool Res() {
    if (m) {
        Kmp();
        return Match();
    }
    return true;
}

void Solve() {
    cin >> n >> m;
    ReadList(s, n);
    ReadList(t, m);
    n--;
    m--;
    cout << (Res() ? "S\n" : "N\n");
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setfill('0');
    Solve();
    return 0;
}