|Online Judge||Problem Set||Authors||Online Contests||User|
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 (p1, p2, p3, p4, …,pn) which satisfies that each element at the position (t1, t2, t3, t4, …,tn) in T is the same as the element at the position (p1 + t1 - 1, p2 + t2 - 1, p3 + t3 - 1, p4 + t4 - 1, …,pn + tn - 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.
The first line contains the positive number n, which is not larger than 10.
The second line contains n positive numbers a1, a2, a3, ...,an, representing the range of each dimension of matrix S.
The third line contains n positive numbers b1, b2, b3, ...,bn, 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 * c2 * c3 * ... * cn in a line, we will give the element at the position (d1, d2, d3, …,dn) in the matrix as the (c2 * c3 * ... * cn * (d1 – 1) + c3 * c4 * ... * cn * (d2 – 1) + ... + cn * (dn - 1 – 1) + dn)–th element in the line.
We guarantee that bi <= ai, 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.
You should output n numbers in a line, p1, p2, p3, …,pn, 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
POJ Monthly--2006.06.25, Long Fan
[Submit] [Go Back] [Status] [Discuss]
Home Page Go Back To top
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator