標籤: 暫無標籤

  BF(Brute Force)演算法核心思想是:首先S[1]和T[1]比較,若相等,則再比較S[2]和T[2],一直到T[M]為止;若S[1]和T[1]不等,則T向右移動一個字元的位置,再依次進行比較。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],則匹配成功;否則失敗。該演算法最壞情況下要進行M*(N-M+1)次比較,時間複雜度為O(M*N)。

  下面是用C語言實現:

  int Index(SString S,SString T,int pos)

  { "

  "

  int i,j;

  if(1<=pos&&pos<=S&#91;0&#93;)

  {

  i=pos;

  j=1;

  while(i<=S&#91;0&#93;&&j<=T&#91;0&#93;)"

  if(S&#91;i&#93;==T&#91;j&#93;) "

  {

  ++i;

  ++j;

  }

  else "

  {

  i=i-j+2;

  j=1;

  }

  if(j>T&#91;0&#93;)

  return i-T&#91;0&#93;;

  else

  return 0;

  }

  else

  return 0;

  }

相關評論

同義詞:暫無同義詞