面接問題61:あいまいな文字列のマッチング

http://blog.csdn.net/v_jurlyuv/articale/detail/6313257
61、騰訊現場求人問題liuchen 1206は今日騰訊の現場募集会に参加しました.このテーマに出会いました.  英語の文章で指定された人名を検索します.人名は26文字(大文字または小文字でもいいです.)、空欄と2つのワイルドカードから構成されています.ワイルドカード「*」は0文字または複数の任意の文字を表し、ワイルドカード「?」は任意の文字を表します.例えば、「J*Smi?」は「John Smith」にマッチすることができます.
C言語で下記の関数を実現してください.void scan(const char*pszText、const char*pszName).注:pszTextは文章全体の文字で、pszNameは英語名にマッチすることを要求します.いくつかの関数を完成して、すべての英語名を出力してください.printf以外は第三者のライブラリ関数などを使うことができません.
私の考え:
入力したターゲット文字列をキーサブ文字列と区切り文字列に分割します.
例えば、入力したターゲット文字列はJ＊ですか?Smiこの2つのキーサブ文字列はJ、Smi、2つの区切り文字列*?最初の区切り文字列は、第1のキーサブ文字列と第2のサブキー文字列の間に少なくとも1文字があり、第2の区切り文字列は、第2のサブ文字列の後に2文字が必要であることを示しています.
注意:ターゲット文字列の開始と終了は*を含んではいけません.無効です.例えば＊?Smi?*?*、このターゲット文字列は何ですか?Smi
アルゴリズムの流れ:
1、入力したターゲット文字列をK個のキーサブ文字列とK＋1個の区切り文字列に分割します.
2、KMP文字マッチングアルゴリズムを使用して、それぞれK個のキーサブ文字列にマッチし、結果キーサブ文字列の位置をそれぞれK個の配列に保存します.
3、K＋1個の区切り文字列の表現の最少文字を計算します.計算方法は*があるだけで表示>=0を表します.N個ありますか?を表す
      1)*だけが、>=0
2)だけですかNは表しますか?の数
3)＊がありますNは表しますか?の個数、例えば*?この場合>=2、例えば*?*、なら>=2
4、Liをi番目のキーサブ文字列の整合個数として定義し、
最初のキーサブ文字列の前の文字数を最初の区切り文字列の条件を満たすかどうかを比較します.
i番目のキーサブ文字列とi＋1番目のキーサブ文字列との間でi＋1番目の区切り文字列の条件が満たされているかどうかを判断し、満足されれば判断を継続します.
K番目のキーサブ文字列の後の文字がK＋1番目の区切り文字列の条件を満たすまで、現在の文字列を出力し、最初のキーサブ文字列の最初の文字からK番目のキーサブ文字列の最後の文字までを出力します.また、1番目とK＋1番目の区切り文字列の中にNiとN k＋1個がありますか?前のNiと後ろのN k＋1文字を出力します.
5,終わります
実装:
1、KMP文字列マッチング関数
// data Charがマッチする文字列、objectターゲット文字列、マッチする文字列の座標、0から開始します.
//maxMatch Num最多記録できるマッチング数は、match Index配列長であり、
//は値を返します.最大マッチ数を超えると-1を返します.マッチしていない場合は0を返します.そうでない場合はマッチした個数を返します.
int KMPMatch(const char*dataChar、const char*object、int*match Index、int maxMatch Num)
2、対象文字列解析
//入力したターゲット文字列 inObject String、キー文字列 subKeyString、
例えば、inObject String=「J*S m i?」はsubKeyString={'J'、'\0'、'S'、'm'、''i'、\0'、}; subKenCharNum={1,3} subKeyStringNum=2;
divAsk={0,0,2} divNum=3;
int parseObject String(const char*inObject String、char*subKeyString、int*subKenCharNum、int subKeyStrigNum、int*divAsk int*divNum)
3、i番目のキーサブ文字列にマッチする
subKeyString Start={0,2}
第iキーサブ文字列とマッチ
 KMPMatch(dataChar,subKeyString[subKeyStringStart[i],maxMatch Index,match Num)
4、マッチング結果に基づいてターゲット文字列全体のマッチング結果を出力する
void check Object String()
KMP実現:
【Cコード-KMP】http://www-igm.univ-mlv.fr/~lecroq/string/node 8.

void preKmp(char *x, int m, int kmpNext[]) {
   int i, j;

   i = 0;
   j = kmpNext[0] = -1;
   while (i < m) {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
   }
}
void KMP(char *x, int m, char *y, int n) {
   int i, j, kmpNext[XSIZE];

   /* Preprocessing */
   preKmp(x, m, kmpNext);

   /* Searching */
   i = j = 0;
   while (j < n) {
      while (i > -1 && x[i] != y[j])
         i = kmpNext[i];
      i++;
      j++;
      if (i >= m) {
         OUTPUT(j - i);
         i = kmpNext[i];
      }
   }
}