Dynamic substitution of conversational services during the execution of service orchestrations is a challenging issue in Service-Oriented Architecture. For a conversational service and its candidate substitute service, there may exist mismatches at interface level as well as protocol level. To make the service substitution consistent, it is essential to implement adaptation to overcome both types of mismatches. In this paper, we present an automatic approach to generate adaptation contract for conversational service substitution. Our approach is based on graph planning technique, which enables us to retrieve a solution in polynomial time. Experiments show that the proposed approach is potentially applicable for on-the-fly service substitution.