#CODEFORCESP7339. Spelling Check
Spelling Check
描述
Petya(皮特娅)注意到当他使用键盘输入时,他经常按下额外的按钮并在单词中添加额外的字母。当然,拼写检查系统会为他标出这些单词,他必须点击每个单词并选择正确的变体。Petya厌倦了自己纠正错误,所以他决定发明一个可以自动纠正单词的函数。Petya从分析最常发生在他身上的情况开始,当需要删除一个字母才能使一个单词与字典中的单词匹配时。因此,Petya面临一个小任务:他有一个打印出的单词和一个来自字典的单词,他应该从第一个单词中删除一个字母以得到第二个单词。现在Petya面临的非常复杂的问题是:他应该删除哪个字母?
输入
输入数据包含两个字符串,由小写拉丁字母组成。每个字符串的长度从1到10^6个字符(包括1和10^6)。第一个字符串比第二个字符串多一个符号。
输出
在第一行输出第一个字符串中符号的位置数,删除这些符号后,第一个字符串变成与第二个字符串相同。在第二行上按递增顺序输出这些符号的位置,位置从1开始编号。如果无法通过删除一个符号使第一个字符串与第二个字符串相同,则输出数字0。
样例
abdrakadabra
abrakadabra
1
3
aa
a
2
1 2
competition
codeforces
0
Description
Petya has noticed that when he types using a keyboard, he often presses extra buttons and adds extra letters to the words. Of course, the spell-checking system underlines the words for him and he has to click every word and choose the right variant. Petya got fed up with correcting his mistakes himself, that’s why he decided to invent the function that will correct the words itself. Petya started from analyzing the case that happens to him most of the time, when all one needs is to delete one letter for the word to match a word from the dictionary. Thus, Petya faces one mini-task: he has a printed word and a word from the dictionary, and he should delete one letter from the first word to get the second one. And now the very non-trivial question that Petya faces is: which letter should he delete?
The input data contains two strings, consisting of lower-case Latin letters. The length of each string is from 1 to 106 symbols inclusive, the first string contains exactly 1 symbol more than the second one.
In the first line output the number of positions of the symbols in the first string, after the deleting of which the first string becomes identical to the second one. In the second line output space-separated positions of these symbols in increasing order. The positions are numbered starting from 1. If it is impossible to make the first string identical to the second string by deleting one symbol, output one number 0.
Input
The input data contains two strings, consisting of lower-case Latin letters. The length of each string is from 1 to 106 symbols inclusive, the first string contains exactly 1 symbol more than the second one.
Output
In the first line output the number of positions of the symbols in the first string, after the deleting of which the first string becomes identical to the second one. In the second line output space-separated positions of these symbols in increasing order. The positions are numbered starting from 1. If it is impossible to make the first string identical to the second string by deleting one symbol, output one number 0.
Samples
abdrakadabra
abrakadabra
1
3
aa
a
2
1 2
competition
codeforces
0
相关
在以下作业中: