Solution Notes: At a high level, all we need to do to solve this problem is to test every window of length C within our larger piece of music to see if it "matches" our chord pattern. The is done in the match() function below, where P[] is a length-C array containing a window from the larger piece of music, and Q[] is a length-C array containing the chord pattern. How do we compare these in a manner that is insensitive to re-ordering and transposition? There are several approaches that would work here; perhaps the simplest is to convert P and Q into a "canonical" form that removes re-ordering and transposition from the picture. For example, if we sort P and Q, then this makes re-ordering no longer matter. We can also shift the contents of P and Q so the minimum in each array is zero. Afterwards, we simply compare P and Q element by element to see if they are equal.
#include <stdio.h>
#define MAX_N 20000
#define MAX_C 10
int A[MAX_N], B[MAX_C], M[MAX_N];
int N, C;
void translate_so_min_is_zero(int *X)
{
int i, min;
for (i=0; i<C; i++)
if (i==0 || X[i]<min)
min = X[i];
for (i=0; i<C; i++)
X[i] -= min;
}
void sort(int *X)
{
int i, j, tmp;
for (i=0; i<C; i++)
for (j=0; j<C-1; j++)
if (X[i] > X[j]) {
tmp = X[i];
X[i] = X[j];
X[j] = tmp;
}
}
/* Return 1 if match at index idx */
int match(int idx)
{
int P[MAX_C], Q[MAX_C];
int i, j, min, tmp;
for (i=0; i<C; i++) {
P[i] = A[i+idx];
Q[i] = B[i];
}
translate_so_min_is_zero(P);
translate_so_min_is_zero(Q);
sort(P);
sort(Q);
for (i=0; i<C; i++)
if (P[i] != Q[i])
return 0;
return 1;
}
int main(void)
{
int i, total = 0;
freopen ("moosick.in", "r", stdin);
freopen ("moosick.out", "w", stdout);
scanf ("%d", &N);
for (i=0; i<N; i++)
scanf ("%d", &A[i]);
scanf ("%d", &C);
for (i=0; i<C; i++)
scanf ("%d", &B[i]);
for (i=0; i+C<=N; i++) {
M[i] = match(i);
total += M[i];
}
printf ("%d\n", total);
for (i=0; i<N; i++)
if (M[i])
printf ("%d\n", i+1);
return 0;
}