| 試題編號： | 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;}
新聞熱點
疑難解答
