PARTIAL CHARACTER STRING POSITION DETECTION DEVICE, PARTIAL CHARACTER STRING POSITION DETECTION METHOD, AND PROGRAM

摘要

The positions in a text in which partial character strings in a pattern appear are efficiently detected. A partial-character-string position detecting device 1 takes inputs of a secret text [t] of a text t, a secrete text p of a pattern p, a secret text c of a vector c, and a secret text E of a matrix E and outputs a secret text H of a matrix H. A first matrix generating part 20 generates a secret text F of a matrix F, in which F[i][j] = E[i][j + i mod n + 1] (where it is assumed that E[i][n] = ¬c[i]). A second matrix generating part 30 generates a secret text F' of a matrix F', in which F[i][j] = 1 is set if c[i] = 0 or if c[i] = 1 and F[k][j] = 1 for every k that is successively c[k] = 1, otherwise F[i][j] = 0 is set, where k = i, ..., n - 1. A third matrix generating part 40 computes H[i][j] = F[i][j - i mod n + 1] ˆ§ c[i] ˆ§ ¬c[i - 1] to generate the secrete text H.