Delete it

Problem A: Delete it

Time Limit: 2 Sec   Memory Limit: 64 MB
Submit: 99   Solved: 25

Description

克林在打一行字母时总是会打多一个字符，比如想打”july”时会打成”juuly”,这样他需要删掉其中一个’u’。

克林想知道他可以删掉哪个位置的字符就可以变成他真正想打的一行字母。

Input

第一行一个整数:T (测试个数)

每个测试

输入两行，两个字符串（全是小写字母）

串长为 1 到 1000000

第一个串长度刚好比第二个的长度大一

Output

每个测试数据：

第一行输出可以删除的位置个数 P

如果P > 0 第二行输出可以删除的位置（小到大，空格隔开，位置从1开始算）

Sample Input

3

juuly

july

abc

zz

aa

a

Sample Output

2

2 3

0

2

1 2

思路：题目意思应该很简单就懂了，关键看用什么方法，题目所给数据不大，可以直接做。

可以由两个指针，一个从前往后扫，一个从后往前扫，比较两个字符串的异同，当比较到不同时，结束扫描。

那么结果就出来了。

代码：

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
#define MAX 1000000
char a[MAX+10],b[MAX+10];
int main()
{
    //freopen("data.in", "r", stdin);
    //freopen("data.out","w",stdout);
    int n,i,len,j;
    scanf("%d",&n);
    while(n--)
    {
        scanf("%s%s",&a,&b);
        len=strlen(b);
        i=0;j=len+1;
        while(i<len&&a[i]==b[i])
            i++;
        while(j-1>0&&a[j-1]==b[j-2])
            j--;
        //printf("i=%d  j=%d\n",i,j);
        if(i-j+2<=0)
            printf("0\n");
        else
        {
            printf("%d\n",i-j+2);
            for(int m=j-1;m<=i;m++)
            {
                if(m==j-1)
                    printf("%d",m+1);
                else
                    printf(" %d",m+1);
            }
            printf("\n");
        }
    }
    return 0;
}