欢迎前往个人搭建博客 Five-great的博客

B: Beyond the Boundry
Time Limit: 1000 MS Memory Limit: 1048576 KB
Total Submit: 98 Accepted: 51 Page View: 407
Submit Status Clarify

Description
There are four students, Kanbara Akihito, Kuriyama Mirai, Nase Hiroomi and Nase Mitsuki, studying in the senior middle school. They all took part in an exam the other day. Now it`s your turn to give papers back to them. However, the names were written so vaguely that you barely recognize any letters of their names.

Given a character string representing the vague name written on the paper, of which the blank has been omitted, you are supposed to output the possible original names of it (which means that after obliterating the blank and some of the characters of the person’s name, it turns into the vague name which is given). If multiple names match the vague name, output all of them in the lexicographical order.

Attention: uppercase letters and lowercase letters are distinctive!

Input
The first line contains a integer T
T
representing the number of test cases.
In each test case, there is a non-empty string s
s
in one line.
It is guaranteed that s contains only English letters and is a subsequence of at least one student’s name.
1≤T≤10000
1≤T≤10000

Output
For each test case, output an integer n in the first line representing the number of students satisfying that s is a subsequence of their names.
There are n lines following (in lexicographical order). Each of them contains a name which might be the original name of the vague name.

Sample Input

Raw

3
NaseMitsuki
a
Ka

Sample Output

Raw

1
Nase Mitsuki
4
Kanbara Akihito
Kuriyama Mirai
Nase Hiroomi
Nase Mitsuki
2
Kanbara Akihito
Kuriyama Mirai

思路： 分别判断4个母串 中 是否存在 递增子序列 与 匹配串相同

AC代码

#include <stdio.h>
#include <string.h>
int main()
{
    int T,i,j,k,now,ans,len;char str[4][20]={"Kanbara Akihito","Kuriyama Mirai","Nase Hiroomi","Nase Mitsuki"};
    int s[4][260][5];char ps[20];int res[5];
    memset(s,0,sizeof(s));
    for(i=0;i<4;i++)
     {  len=strlen(str[i]);
      for(j=0;j<len;j++)
       { k=0;
        while(s[i][str[i][j]][k])k++;//判断是否前面出现过该字符 
          s[i][str[i][j]][k]=j+1;//位置从1开始 所以 j+1; 
		//在第i个字符串中第 j 个字符在该字符串的位置 
		 //0 1 2 3 4 5 6 j
		// K a n b a r a 
		// s[i][str[i][j]][k]=j+1;
		// s[0][str[0][6]][3]=j+1;
		// s[0][97][3]=7;
		// {s[0][97][2]=5;
		// s[0][97][3]=2;}
       }
	 }
    scanf("%d\n",&T);
    while(T--)
    {  memset(res,0,sizeof(res));ans=0;
        gets(ps);
        len=strlen(ps);
        for(i=0;i<4;i++)
        {   now=0;
            for(j=0;j<len;j++)
            {  k=0;
                while(now>=s[i][ps[j]][k]&&k<4)k++;//判断是否有匹配但前字符且
                if(k==4)break;  //未匹配 成功 // 在母串中位置比上一个匹配字符位置大 
                now=s[i][ps[j]][k];//更新当前匹配 
            }
            if(j==len)res[i]=i+1,ans++;//符合条件 存入结果数组 
        }
        printf("%d\n",ans);
        for(i=0;i<5;i++)
        if(res[i])printf("%s\n",str[res[i]-1]);
    }
    return 0;
}