N-dimension Matching
Description
Let us consider an n-dimension matching problem of two matrices. Here the index number of each dimension of a matrix starts at 1. For two n-dimension matrixes S and T, if there is a position (p
1, p
2, p
3, p
4, …,p
n) which satisfies that each element at the position (t
1, t
2, t
3, t
4, …,t
n) in T is the same as the element at the position (p
1+ t
1- 1, p
2+ t
2- 1, p
3+ t
3- 1, p
4+ t
4- 1, …,p
n+ t
n- 1) in S, we call it’s a matching position. So the n-dimension problem is to compute the matching position for given S and T. You can assume that the traditional string matching problem is the 1-dimension version of this problem, and the normal matrix matching problem is the 2-dimension version.
Input
The first line contains the positive number n, which is not larger than 10.
The second line contains n positive numbers a1, a
2, a
3, ...,a
n, representing the range of each dimension of matrix S.
The third line contains n positive numbers b1, b
2, b
3, ...,b
n, representing the range of dimensions of matrix T.
The fourth line gives the elements in S. The fifth line gives the elements in T.To give out an n-dimension matrix with size c1
* c
2* c
3* ... * c
nin a line, we will give the element at the position (d
1, d
2, d
3, …,d
n) in the matrix as the (c
2* c
3* ... * c
n* (d
1– 1) + c
3* c
4* ... * c
n* (d
2– 1) + ... + c
n* (d
n - 1– 1) + d
n)–th element in the line.
We guarantee that bi<= a
i, elements in S and T are all positive integers that are not larger 100, and the number of the elements in S and T are both not larger than 500000.
Output
You should output n numbers in a line, p
1, p
2, p
3, …,p
n, representing the matching position. Please print the lexically smallest one if there are many. We guarantee that there is at least one matching position.
2
4 4
2 2
3 2 1 1 2 2 2 1 1 2 2 2 1 1 2 2
2 2 2 2
2 2Source
POJ Monthly--2006.06.25, Long Fan