模式匹配

1、首先学习最简单的模式匹配问题，其实就是查找字符串的问题，问题简单描述：从一段英文字符串中查找某一个单词或一个简短的字符串，并记录下该单词在整个字符串的位置，也即起始索引

在下列一组文本行中查找包含字符串”ould“的行：

Ah Love! could you and I with Fate conspire

To grasp this sorry Scheme of Things entire,

Would not we shatter it to bits and then

Remould it nearer to the Heart's Desire!

程序执行后输出下列结果：

Ah Love! could you and I with Fate conspire

Would not we shatter it to bits and then

Remould it nearer to the Heart's Desire!

先上代码：

 1 #include <stdio.h>
 2 #define MAXLINE 1000 /* maximum input line length */
 3 int getline(char line[], int max)
 4 int strindex(char source[], char searchfor[]);
 5 char pattern[] = "ould"; /* pattern to search for */
 6 /* find all lines matching pattern */
 7 main()
 8 {
 9 char line[MAXLINE];
10 int found = 0;
11 while (getline(line, MAXLINE) > 0)
12 if (strindex(line, pattern) >= 0) {
13 printf("%s", line);
14 found++;
15 }
16 return found;
17 }
18 /* getline: get line into s, return length */
19 int getline(char s[], int lim)
20 {
21 int c, i;
22 i = 0;
23 while (lim
24 > 0 && (c=getchar()) != EOF && c != '
')
25 s[i++] = c;
26 if (c == '
')
27 s[i++] = c;
28 s[i] = '';
29 return i;
30 }
31 /* strindex: return index of t in s, 1
32 if none */
33 int strindex(char s[], char t[])
34 {
35 int i, j, k;
36 for (i = 0; s[i] != ''; i++) {
37 for (j=i, k=0; t[k]!='' && s[j]==t[k]; j++, k++)
38 ;
39 if (k > 0 && t[k] == '')
40 return i;
41 }
42 return 1;
43 }

View Code

字符串匹配的KMP算法