KMP算法的应用。

1 #include 
     
       2 #include 
      
        3  4 #define MAXNUM 100005 5  6 char src[MAXNUM], des[MAXNUM]; 7 char src1[MAXNUM*2], des1[MAXNUM*2]; 8 int next[MAXNUM]; 9 10 void getnext(char *p, int *next, int len) {11     int j, k;12     j = 0;13     k = -1;14     next[0] = -1;15     while (j+1 < len) {16         if (k==-1 || p[j]==p[k]) {17             ++j;18             ++k;19             if (p[j] == p[k])20                 next[j] = next[k];21             else22                 next[j] = k;23         } else {24             k = next[k];25         }26     }27 }28 29 int kmp(char *src, char *des, int lens, int lend) {30     int i, j;31 32     i = j = 0;33     memset(next, 0, sizeof(next));34     getnext(des, next, lend);35     while (i < lens) {36         while (src[i] != des[j]) {37             if (next[j] == -1) {38                 j = 0;39                 break;40             }41             j = next[j];42         }43         if (src[i] == des[j])44             ++j;45         ++i;46     }47 48     return j;49 }50 51 int main() {52     int i, j, k;53     char *p, *q;54     int lens, lend;55 56     while (scanf("%s %s", src, des) != EOF) {57         lens = strlen(src);58         lend = strlen(des);59         j = kmp(src, des, lens, lend);60         k = kmp(des, src, lend, lens);61         if (j == k) {62             strcpy(src1, src);63             for (i=j; i
       
         k) {77             p = src;78             q = des;79         } else {80             p = des;81             q = src;82             j = k;83         }84         printf("%s", p);85         printf("%s\n", q+j);86     }87 88     return 0;89 }