生活随笔
收集整理的这篇文章主要介绍了
匹配串 KMP算法
小编觉得挺不错的,现在分享给大家,帮大家做个参考.
匹配串---基础写法 ：
#include <stdio.h>
#include <string.h> //库函数
/*char * strstr(char *string, char *pattern);
*/
typedef char* Position; //重命名
#define NotFound NULLint main()
{char string[] = "This is a simple example.";char pattern[] = "simple";Position p = strstr(string, pattern);printf("%s\n", p);return 0;
}
KMP算法 ：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef int Position; //起别名
#define NotFound -1 //定义一个不可能是下标的量void BuildMatch(char *pattern, int *match)
{Position i, j;int m = strlen(pattern);match[0] = -1;for (j = 1; j < m; j++){i = match[j - 1];while ((i >= 0) && (pattern[i + 1] != pattern[j]))i = match[i];if (pattern[i + 1] == pattern[j])match[j] = i + 1;elsematch[j] = -1;}
}Position KMP(char *string, char *pattern)
{int n = strlen(string);int m = strlen(pattern);Position s, p, *match;if (n < m)return NotFound;match = (Position *)malloc(sizeof(Position) * m);BuildMatch(pattern, match);s = p = 0;while (s < n && p < m){if (string[s] == pattern[p]){s++;p++;}else if (p > 0)p = match[p - 1] + 1;elses++;}return (p == m) ? (s - m) : NotFound;
}int main()
{//char string[] = "This is a simple example.";//char pattern[] = "sample";printf("请输入字符串1 ：\n");char string[81];// scanf("%s",string);gets(string);//getchar();printf("请输入字符串2 ：\n");char pattern[81];//scanf("%s",pattern);gets(pattern);//返回字符指针,只能处理字符串;返回数组下标,可处理任何类型串Position p = KMP(string, pattern); //返回数组下标if (p == NotFound)printf("NotFound.\n");elseprintf("字符串匹配成功：%s\n", string + p);return 0;
}
总结
以上是生活随笔为你收集整理的匹配串 KMP算法的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
