KMP算法-C語言程序實現

    //////////////////////////////////////////////////

    /KMP算法/


#include<stdio.h>  
#include<string.h>  
#include<iostream>  
using namespace std;  

void getNext(char a[],int next[]){  
    int i,j;  
    next[1] = 0;  
    j = 0;  
    i = 2;  
    int m = strlen(a)-1; //從a[1]開始   
    while(i<=m){  
        if(a[j+1] == a[i]){  
            j++; next[i++] = j;  
        }  
        else if(j==0){  
            next[i++] = 0;  
        }else if(j>0){  
            j = next[j];  
        }   
    }  
}  
int match(char a[],char b[],int next[]){  
    int i=0,j=0;  
    int pos;  
    int n = strlen(a)-1;  
    int m = strlen(b)-1;  
    while(1){  
        if(i>n) {  
            pos = -1; break;  
        }  
        if(j==m){  
            //pos = i-j+1; break;  
            cout<<i-j+1<<"  "<<endl; j=next[j];  
        }  
        if(b[j+1] == a[i+1] ){  
            j++; i++;  
        }else{  
            if(j==0) i++;  
            else if (j>0){  
                j = next[j];  
            }  
        }  
    }     
}   
/*  
int main() 
{    
    //char b[] = "!ababbc";  
    char b[] = "!abab";  
    int l = strlen(b); 
    int *next = new int[l-1]; 
    getNext(b,next); 
    int i; 
    for(i=1;i<=l-1;i++){ 
        printf("%d ",next[i]); 
    } 
    cout<<endl; 
    char a[] = "!ababababbc"; 
    int pos = match(a,b,next); 
    cout<<endl<<pos<<endl; 
} 
*/  
//////////////////////////////////////////////////////  
/* 
KMP應用： 求一個串中所有前綴等于后綴的子串長度  
*/  
void output(int i,int next[]){  
    while(next[i]>0){  
        cout<<next[i]<<" ";  
        i = next[i];  
    }  
}  
/* 
int main() 
{    
    char b[] = "!ababa";  
    int l = strlen(b); 
    int *next = new int[l-1]; 
    getNext(b,next); 
    int i; 
    for(i=1;i<=l-1;i++){ 
        printf("%d ",next[i]); 
    } 
    cout<<endl; 
    output(l-1,next); 
    delete[] next; 
} 
*/  </pre>