博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
kmp 算法
阅读量:5278 次
发布时间:2019-06-14

本文共 1312 字,大约阅读时间需要 4 分钟。

#include 
#include
#include
int next[1000]; int nextval[1000]; void get_next(char *str) {
int i = 1 , j = 0, len; str[0] = strlen( (str + 1)); next[1] = 0; while ( i < str[0] ) {
if ( j == 0 || str[i] == str[j] ) i++, j++, next[i] = j; else j = next[j]; } } void get_nextval ( char *str) {
int i = 1, j = 0; nextval[1] = 0; str[0] = strlen (str + 1); while ( i < str[0] ) {
if (str[i] == str[j] || j == 0) {
i++, j++; if (str[i] != str[j] ) nextval[i] = j; else nextval[i] = nextval[j]; } else j = nextval[j]; } } int index_kmp ( char *S, char *T) {
int i = 1, j = 1; S[0] = strlen(S + 1); T[0] = strlen(T + 1); while ( i <= S[0] && j <= T[0]) {
if ( j == 0 || T[j] == S[i] ) {
i++, j++; } else j = nextval[j]; } if ( j > T[0]) return i - T[0]; return 0; } int main( ) {
char ch[30]; char sh[100]; while (scanf("%s%s",sh+1, ch+1) != EOF ) {
memset(next, 0, sizeof(next)); get_next(ch); get_nextval(ch); printf("%d\n",index_kmp(sh,ch)); } return 0; }

转载于:https://www.cnblogs.com/tangcong/archive/2011/07/24/2115351.html

你可能感兴趣的文章
浅说 apache setenvif_module模块
查看>>
MySQL--数据插入
查看>>
重新学习python系列(二)? WTF?
查看>>
shell脚本统计文件中单词的个数
查看>>
SPCE061A学习笔记
查看>>
sql 函数
查看>>
hdu 2807 The Shortest Path 矩阵
查看>>
熟悉项目需求,要知道产品增删修改了哪些内容,才会更快更准确的在该项目入手。...
查看>>
JavaScript 变量
查看>>
java实用类
查看>>
smarty模板自定义变量
查看>>
研究称90%的癌症由非健康生活习惯导致
查看>>
命令行启动Win7系统操作部分功能
查看>>
排序sort (一)
查看>>
Parrot虚拟机
查看>>
Teamcenter10 step-by-step installation in Linux env-Oracle Server Patch
查看>>
Struts2学习(三)
查看>>
Callable和Runnable和FutureTask
查看>>
GitHub 多人协作开发 三种方式:
查看>>
文本域添加编辑器
查看>>