1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75
| #include <stdio.h> #include <stdlib.h> #include <string.h>
#define MAX 101
void get_next( int *next,char *a,int la) { int i=1,j=0 ; next[1] = 0 ; while ( i <= la) { if( a[i] == a[j] || j == 0 ) { j ++ ; i ++ ; if( a[i] == a[j]) next[i] = next[j]; else next[i] = j ; } else j = next[j] ; } }
int str_kmp( int *next, char *A ,char *a, int lA,int la) { int i,j,k ; i = 1 ; j = 1 ; while ( i<=lA && j <= la ) { if(A[i] == a[j] || j == 0 ) { i ++ ; j ++ ; } else j = next[j] ; } if ( j> la) return i-j+1 ; else return -1 ; }
int main(void) { int n,k; int next[MAX]={0} ; int lA=0,la =0 ; char A[MAX],a[MAX] ; scanf("%s %s",A,a) ; lA = strlen(A); la = strlen(a); for(k=la-1; k>= 0 ;k --) a[k+1] = a[k] ; for(k=lA-1; k>= 0 ;k --) A[k+1] = A[k] ; get_next(next,a,la) ; k = str_kmp(next,A,a,lA,la); if ( -1 == k) printf("Not Soulation!!! "); else printf("%d ",k) ; system("pause"); return 0 ; }
|