模式匹配 KMP算法收藏

#include<iostream>

using namespace std;

typedef struct String
{
    char* str;
    int length;
};

void getString(String s)
{
       cin >> s.str;
       s.length = strlen(s.str);
}

void  getNext(String pattarn, int *next)
{
       int i = 0, j = -1,  n = pattarn.length;
 
       next[0] = -1;
 
       while( i < n-1 )
       {
              if( j== -1 || pattarn.str[i] == pattarn.str[j])
              {
                     j++; i++;
                     next[i] = j;    
              }
              else
              {
                     j = next[j];
              }
       }
}

int subString(String s, String pattarn)
{
       int n = s.length,
             m = pattarn.length,
            *next = new int[n],
            i = 0,
            j = 0;
    
      getNext(pattarn, next);
 
      while( i < n && j < m )
      {
           if( j == -1 || s.str[i] == pattarn.str[j])
           {
                  i++; j++;
           }
           else
           {
                  j = next[j];
           }    
       }
 
       delete next;
    
       if( j == m)
              return i - m;
       else
              return -1;
}

int main(){
       String s,c;
 
       /**//*getString(s);*/
       s.str = "ababcbababac";
       s.length = 12;
       c.str = "babac";
       c.length = 5;
    
       cout <<subString(s,c) << " ";
       return 0;
}

posted on 2008-08-23 11:58 弱水一瓢 阅读(136) 评论(0)  编辑 收藏 引用 所属分类: Data Structure