1.算法的思想##

看了一下一個(gè)老外的博客提完，他把kmp簡(jiǎn)單的過了一遍百新，非常簡(jiǎn)潔珊燎，貌似一下子看懂了不少檬贰。他的博客地址姑廉。

2.代碼實(shí)現(xiàn)##

//
//  main.cpp
//  leetcode
//
//  Created by YangKi on 15/11/12.
//  Copyright ? 2015年 YangKi. All rights reserved.
//  本版本的kmp找到第一個(gè)符合的子字符串就跳出返回結(jié)果

#include<cstdlib>
#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int kmp( char * pattern, int l1, char* words, int l2 )
    {
        if (l1>l2) {
              printf("can't find\n");
            return -1;
        }
        int *next=new int[l1]; //跳躍數(shù)組
        next[0]=0;
        
        //1.根據(jù)pattern構(gòu)造next數(shù)組
        for (int i=1; i<l1; i++)//字長(zhǎng)為1的不算前綴后綴,i指向當(dāng)前長(zhǎng)度的字符串的結(jié)尾
        {
            int j=(i+1)-1;
            for(; j>=1; j--)//j為考察的前/后綴長(zhǎng)度
            {
                if ( cmp(pattern, pattern+i-(j-1), j)==true ) {
                    next[i]=j;
                    break;
                }
            }
            if(j==0) next[i]=0;
        }
        
        //for(int i=0; i<l1; i++)printf("%d ", next[i]);
        
        
        //2.開始搜索子字符串，用next數(shù)組跳
        for( int i=0; i<=l2-l1; )
        {
            int tempi=i;//用于對(duì)比翁涤，是大數(shù)組的指針
            int partial_length=0;
            
            for(int j=0; j<l1; j++, tempi++)
            {
                if(pattern[j] != words[tempi])
                {
                    break;
                }
                else
                {
                    partial_length++;
                }
            }
            
            if(partial_length>1)
            {
                if(partial_length==l1)//找到了,本版本的kmp找到第一個(gè)符合的子字符串就跳出返回結(jié)果
                {
                    printf("the first substring index is %d\n", i);
                    return i;
                }
                else//要借用next數(shù)組去跳
                {
                    i+= ( partial_length - next[partial_length - 1] );
                }
            }
            else//partial_length==0,1 都只跳一位
            {
                i++;
            }
            
        }
        
        printf("can't find\n");
        return -1;
    }
    
private:
    bool cmp(char* c1, char* c2, int length)
    {
        for (int i=0; i<length; i++)
        {
            if(c1[i] != c2[i]) return false;
        }
        return true;
    }
};

int main()
{
    
    Solution *s = new Solution();
    char c1[8]={'a', 'b', 'a', 'b', 'a', 'b', 'c', 'a'};
    char c2[20]={"ababababca"};
    s->kmp(c1, 8, c2, 12);
    
    return 0;
}