寻找部分序列

Time Limit:1000MS  Memory Limit:65536K
Total Submit:139 Accepted:17

Description

若s为一个字符串，把其中(任何位置)的字符去掉，留下的内容为s的一个子序列，也叫部分序列。例如：s为"abcdefg", 去掉b,d,f,剩下"aceg"；去掉a,b,c,剩下"defg"；于是"aceg","defg"都是字符串s的部分序列。请编程判断一个字符串是不是另一个的部分序列。

Input

输入两行：(输入的字符串均不为空字符串，且长度都不大于255)
第一行为字符串s。
第二行为一个字符串p。
判断p是不是s的一个部分序列。

Output

如果p不是s的部分序列，输出No；如果是，则输出两行，第一行为Yes，第二行为字符串p中各个字符在s中的序号(从1开始)。

Sample Input

aabbccdd
abc

abcdefg
agh

Sample Output

Yes
1 3 5
(注意不能是1 3 5以外的，比如2 3 5， 1 4 6等，也即是最左边匹配的部分序列的序号,本句不输出，呵呵~~~)
No

Source

#include <iostream>
#include <string>

using namespace std;

int main()
{
 char Source[300],Str[300];
 int i,j,LenSource,LenStr,Pos[300];
 bool Find;

 gets(Source);
 gets(Str);
 LenStr=int(strlen(Str));
 LenSource=int(strlen(Source));
 Pos[0]=-1;
 for (i=0;i<=LenStr-1;i++)
 {
  Find=false;
  for (j=Pos[i]+1;j<=LenSource-1;j++)
   if (Source[j]==Str[i])
   {
    Pos[i+1]=j;
    Find=true;
    break;
   }
   if (!Find) break;
 }
 if (Find)
 {
  cout<<"Yes\n";
  for (i=1;i<=LenStr;i++) cout<<Pos[i]+1<<' ';
  cout<<'\n';
 }
 else cout<<"No"<<endl;
 return 0;
}