2018四川省大学程序设计竞赛(ACM)B: Beyond the Boundry ----------C语言——菜鸟级
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;
}
相关文章
- PAT乙级1009. 说反话(C语言)
- 深入浅出PID控制算法(三)————增量式与位置式PID算法的C语言实现与电机控制经验总结
- C语言 编写“剪刀石头布”小游戏[通俗易懂]
- 蓝桥杯 历届试题 地库取宝(深搜 dfs)----------C语言—菜鸟级
- C语言空格代码_c语言中空格是字符吗
- C++基础入门_C语言入门基础
- 【已解决】spring boot项目从mysql中获取数据候错误The driver has not received any packets from the server
- 解决The HTTP request is not acceptable for the requested resource
- c语言程序设计总结心得-C语言程序设计小结
- Error fetching command 'build_solr_schema': The 'solr' backend requires the installation of 'pysolr'
- ORA-22900: the SELECT list item of THE subquery is not a collection type ORACLE 报错 故障修复 远程处理
- ORA-26748: The one-to-one transformation function string encountered the following error: string ORACLE 报错 故障修复 远程处理
- ORA-27611: Smart I/O failed due to a block corruption detected on the host. The block was received from cell “string”. disk: “string”, block: “string”, disk offset: “string” ORACLE 报错 故障修复 远程处理
- ORA-32341: The EXPLAIN_MVIEW facility failed to explain the materialized view “string”.”string” ORACLE 报错 故障修复 远程处理
- ORA-46011: The value of the “selectPrivilege” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-46014: The value of the “aclFile” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-46015: The value of the “paramDatatype” element is too long. ORACLE 报错 故障修复 远程处理
- ORA-48414: The string in the execution option exceeds maximum length [string] ORACLE 报错 故障修复 远程处理
- ORA-48490: The field number exceeds the maximum number [string] ORACLE 报错 故障修复 远程处理
- ORA-53010: The value of the tag is null. ORACLE 报错 故障修复 远程处理
- ORA-53035: The rows for the mapping document (string) do not exist. ORACLE 报错 故障修复 远程处理
- ORA-13703: The snapshot pair [string, string] for database_id string and instance_id string are not found in the current repository. ORACLE 报错 故障修复 远程处理
- 彻底搞定C语言指针(精华版)详解编程语言
- Linux C语言实现文件快速排序(linuxc文件排序)
- C语言Linux系统内存管理策略(clinux内存使用)
- 有参函数,C语言有参函数详解
- Linux下安装C语言编译器的指南(linux安装c语言)
- MySQL库类提高C语言编程效率(c mysql库类)
- C语言与Oracle数据库实现模糊查询(c oracle模糊查询)
- C语言与Oracle数据库的新增应用(c oracle 新增)
- 字段C语言 CentOS环境下Oracle四种字段类型深度介绍(c oracle 四种)
- C语言解决不用+、-、×、÷数字运算符做加法的实现方法
- C语言之free函数以及野指针介绍