この問題では「SとTが前から何番目まで一致しているか」と「SとTが後ろから何番目まで一致しているか」 を先に調べることによってO(N)で問題を解くことができます。 例えば aaabbbccc と a?a?b?c の場合 前から調べると T T T T T T T a a a b b b c c c a ?…