数据结构实验之串一:KMP简单应用

2/10/2017来源:ASP.NET技巧人气:293

PRoblem Description 给定两个字符串string1和string2,判断string2是否为string1的子串。 Input 输入包含多组数据,每组测试数据包含两行,第一行代表string1(长度小于1000000),第二行代表string2(长度小于1000000),string1和string2中保证不出现空格。 Output 对于每组输入数据,若string2是string1的子串,则输出string2在string1中的位置,若不是,输出-1。 Example Input

abc a 123456 45 abc ddd

Example Output

1 4 -1

Hint

Author cjx

#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #define N 1010000 using namespace std; void getnext(int *next, char *p)//next数组的获取 { int i=-1, j=0; next[0]=-1; while(p[j++]!='\0') { while(p[j]!=p[i+1]&&i>=0) i=next[i]; if(p[j]==p[i+1])next[j]=i++; else next[j]=-1; } } int kmp(char *str1, char *str2, int *next)//KMP算法 { int lstr1=strlen(str1); int lstr2=strlen(str2); int i=-1, j=0; while(i<lstr1-1&&j<lstr2) { if(str1[i+1]==str2[j]) { i++; j++; } else if(i<0)j++; else if(i>=0)i=next[i]; } return (i==lstr1-1)?(j-i):-1; } int main() { char str[ N ] = {0}; char ptr[ N ] = {0}; int next[ N ]; while( ~scanf( "%s%s", str, ptr ) ) { getnext( next, ptr); printf( "%d\n", kmp( ptr,str,next) ); } return 0; }

kmp有不同的实现形式,主要是不同的next数组的获取方法#include

include

include

include

define N 1010000

using namespace std;

void getnext(int *next, char *p) { int i=-1, j=0; next[0]=-1; while(p[j++]!=’\0’) { while(p[j]!=p[i+1]&&i>=0) i=next[i]; if(p[j]==p[i+1])next[j]=i++; else next[j]=-1; } } int kmp(char *str1, char *str2, int *next) { int lstr1=strlen(str1); int lstr2=strlen(str2); int i=-1, j=0; while(i