思维题,首先肯定可以在2个操作以内让它们相等,即每次选中一个字符串的前缀,转变为相同的那个字符。
考虑如何在一个操作内让它们相等。先找到最长的后缀,假设后缀的起始位置为i,如果s或t的前i-1的前缀都等于一个字符c,那么让另外一个字符串变成这个c即可。
当s就等于t时答案为0。所以对所有情况分类一下即可。
小美有两个长度相等的字符串,第一个字符串为 s ,第二个字符串为 t 。
小美每次可以选择一个字符串的一个前缀,然后选择一个字母 c ,将选择的前缀的所有字母都变成 c 。
小美想知道她最少要操作几次可以使得 s 和 t 相等。
第一行输入一个长度不超过 105 的字符串s 。
第二行输入一个长度与 s 相等的字符串 t 。
第一行输出一个整数m表示答案。
接下来 m 行,每行输出用空格隔开的 i,j,c 表示选择第 i 个字符串的长度为 j 的前缀,将前缀所有字母变成 c 。
输入
aabc
abcc
输出
2
2 3 b
2 2 a
说明
第1次操作选择第2个字符串的长度为3的前缀,将前缀所有字母变成 'b' ,字符串变成 "bbbc" 。
第2次操作选择第2个字符串的长度为2的前缀,将前缀所有字母变成 'a' ,字符串变成 "aabc" 。