/*

*   kmp.cpp

*   Author: Qiang Xiao

*   Time: 2015-07-18

*/

#include<iostream>

#include<string>

using namespace std;

int kmp(string& ma, string& sub, int a[]);

int max_fix_len(string& a, int len);    

int main(){

    string ma= "ABCCBB";

    string sub= "CCB";

    int dis[sub.length()];

    dis[]= -;

    for(int i= ; i< sub.length(); i++){

    dis[i]= max_fix_len(sub, i+);

    }

    int km= kmp(ma, sub, dis);

    cout<<ma<<endl<<sub<<endl;

    cout<<km<<endl;

    return ;

}

int max_fix_len(string& a, int len){

    int ll= ;    //ll denotes the length of prefix, perspectively.

    int maxLen= ;

    while(ll< len){

    int j;

    for(j= ; j< ll; j++){

        if(a.at(j)!= a.at(len+j-ll))

        break;

    }

    if(j== ll- )

        maxLen= ll- ;

    ll++;

    }

    return maxLen;

}

int kmp(string& ma, string& sub, int dis[]){

    int lens= sub.length();

    int lenm= ma.length();

    int wai= ;

    while(wai< lenm- lens){

    int nei1= ;    //sub

    int nei2= wai;    //ma

    for(nei1= ; nei1< lens; nei1++){

        if(ma.at(nei2)== sub.at(nei1)){

        nei1++;

        nei2++;

        }

        else{

        nei1++;

        break;

        }

    }

    if(nei1== lens){

        return wai+ ;

    }

    wai= wai+ nei1- dis[nei1- ]- ;

    }

    return -;

}

xiaoq@xq-ubun:~/C/DataStructure$ g++ kmp.cpp -o kmp.o

xiaoq@xq-ubun:~/C/DataStructure$ ./kmp.o

ABCCBB

CCB

xiaoq@xq-ubun:~/C/DataStructure$