PRoblem Description 给定两个字符串string1和string2，判断string2是否为string1的子串。 Input 输入包含多组数据，每组测试数据包含两行，第一行代表string1(长度小于1000000)，第二行代表string2（长度小于1000000），string1和string2中保证不出现空格。 Output 对于每组输入数据，若string2是string1的子串，则输出string2在string1中的位置，若不是，输出-1。 Example Input
abca12345645abcdddExample Output
14-1Hint
Author cjx
#include <iostream>#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 1010000using 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
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
新闻热点
疑难解答
