- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- void get_nextval(char* str,int* T,int n)
- {
- int i=1,j=0;
- T[0]=0;
- T[1]=0;
- while(i < n)
- {
- if(j == 0 || str[i] == str[j])
- {
- i++,j++;
- if(str[i] != str[j])
- T[i] = j;
- else
- T[i] = T[j];
- }
- else
- j = T[j];
- }
- }
- int Index_kmp(char *str,char* pattern,int pos)
- {
- int i = pos;
- int j = 0;
- int len_str = strlen(str);
- int len_pattern = strlen(pattern);
- int *next = (int *)malloc(sizeof(int) * len_pattern);
- get_nextval(pattern,next,len_pattern - 1);
- while(i < len_str && j < len_pattern)
- {
- if(j == 0 || str[i] == pattern[j])
- {
- if(str[i] == pattern[j])
- {
- i++;
- j++;
- }
- else if(j == 0)
- i++;
- }
- else j = next[j];
- }
- if(j >= len_pattern)
- return i - len_pattern;
- else
- return -1;
- }
- int main(int argc,char* argv[])
- {
- //char *p = "aaaab";
- int next[256];
- char str[256];
- char pattern[256];
- printf("please input the string\\n");
- scanf("%s",str);
- printf("please input the pattern\\n");
- scanf("%s",pattern);
- /*int n = strlen(str);
- get_nextval(str,next,n-1);
- int i;
- for(i=0;i < n;i++)
- {
- printf("%d ",next[i]);
- }
- printf("\\n");*/
- int pos = Index_kmp(str,pattern,0);
- printf("pos = %d\\n",pos);
- }
- //该片段来自于http://www.codesnippet.cn/detail/051220137794.html
来源: http://www.codesnippet.cn/detail/051220137794.html