P8597 [Lanqiao Cup 2013 NOI Qualifier B] Flipping Coins

Xiaoming is playing a game called “flipping coins”.

There are several coins on the table arranged in a row. We use `*` to represent heads and `o` to represent tails (the lowercase letter, not zero). For example, one possible situation is `**oo***oooo`. If we flip the two coins on the left at the same time, it becomes `oooo***oooo`. Now Xiaoming’s question is: given the initial state and the target state, and each move can only flip two adjacent coins at the same time, for a specific configuration, what is the minimum number of flips needed?

Two strings of equal length, one per line, representing the initial state and the target state. The length of each line is less than $1000$. The testdata guarantees that there is at least one way to transform from the initial state to the target state.

One integer, the minimum number of operations.

source: Lanqiao Cup 2013 NOI Qualifier B Group, Problem H. Translated by ChatGPT 5