A server having an automaton whose state transitions in accordance with received characters, determines whether the automaton has transitioned to a final state on the basis of the characters. The server receives a coding sequence from the client in the characters included in the string. The coding sequence elements corresponding to the characters are values encrypting a non-unity using a first encryption scheme having homomorphism, and whose elements not corresponding to the characters are values encrypting a unity using the first encrypting scheme. The server generates, in response to receiving the coding sequence, exchange data encrypting a subsequent state key corresponding to each of a plurality of previous states of the automaton on the basis of the coding sequence using the first encryption scheme; encrypts exchange data with the corresponding previous state key and sends the encrypted exchange data to the client.