| 试题编号： | 201409-3 |
| 试题名称： | 字符串匹配 |
| 时间限制： | 1.0s |
| 内存限制： | 256.0MB |
| 问题描述： | 问题描述 给出一个字符串和多行文字，在这些文字中找到字符串出现的那些行。你的程序还需支持大小写敏感选项：当选项打开时，表示同一个字母的大写和小写看作不同的字符；当选项关闭时，表示同一个字母的大写和小写看作相同的字符。输入格式 输入的第一行包含一个字符串S，由大小写英文字母组成。 第二行包含一个数字，表示大小写敏感的选项，当数字为0时表示大小写不敏感，当数字为1时表示大小写敏感。 第三行包含一个整数n，表示给出的文字的行数。 接下来n行，每行包含一个字符串，字符串由大小写英文字母组成，不含空格和其他字符。输出格式 输出多行，每行包含一个字符串，按出现的顺序依次给出那些包含了字符串S的行。样例输入Hello15HelloWorldHiHiHelloHiHiGrepIsAGreatToolHELLOHELLOisNOTHello样例输出HelloWorldHiHiHelloHiHiHELLOisNOTHello样例说明 在上面的样例中，第四个字符串虽然也是Hello，但是大小写不正确。如果将输入的第二行改为0，则第四个字符串应该输出。评测用例规模与约定 1<=n<=100，每个字符串的长度不超过100。 |
问题链接：CCF201409试题。
问题描述：参见上文。
问题分析：这是一个简单的字符串处理问题，关键是对有关字符串处理函数是否熟悉。这里采用KMP算法实现。
程序说明：有关字符串的处理，这里采用用C语言的函数实现。
相关链接：CCF201409-3 字符串匹配（100分）。
提交后得100分的C++语言程序如下：
/* CCF201409-3 字符串匹配 */#include <iostream>#include <cstring>using namespace std;// KMP算法：函数getnext()和kmp()void getnext(int next[], char t[]){ int i=0, j=-1; next[0] = -1; while(t[i]!='/0') if(j == -1 || t[i] == t[j]) next[++i] = ++j; else j = next[j];}int kmp(int next[], char s[], char t[]){ int i=0, j=0, len1=strlen(s), len2=strlen(t); while(i < len1 && j < len2) { if(j == -1 || s[i] == t[j]) ++i, ++j; else j = next[j]; } if(j>=len2) return i-len2+1; else return -1;}const int MAXN = 100;int next[MAXN+1];char s[MAXN+1], s2[MAXN+1], t[MAXN+1];int main(){ int option, m; cin >> t >> option; if(option == 0) for(int i=0; t[i]; i++) t[i] = tolower(t[i]); getnext(next, t); cin >> m; while(m--) { cin >> s; strcpy(s2, s); if(option == 0) for(int i=0; s2[i]; i++) s2[i] = tolower(s2[i]); if(kmp(next, s2, t) != -1) cout << s << endl; } return 0;}
新闻热点
疑难解答
