PRoblem Description 給定兩個字符串string1和string2，判斷string2是否為string1的子串。 Input 輸入包含多組數(shù)據(jù)，每組測試數(shù)據(jù)包含兩行，第一行代表string1(長度小于1000000)，第二行代表string2（長度小于1000000），string1和string2中保證不出現(xiàn)空格。 Output 對于每組輸入數(shù)據(jù)，若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數(shù)組的獲取{ 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有不同的實現(xiàn)形式，主要是不同的next數(shù)組的獲取方法#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
新聞熱點
疑難解答
