Агуулга: Энэ бүлэгт ашигласан программын кодуудыг энд үзүүллээ. Mаш олон хэрэглээнд тодорхой нэг тэмдэгт мөрийг хайхаас гадна тэмдэгт мөрийг ямар нэг хэв шинжээр олж авах шаардлага гардаг. Хайх хэв шинжийг илэрхийлэх загварт хамгийн тохиромжтой, уян хатан арга бол тэмдэгтүүд болон үйлдлээс тогтох хэвийн илэрхийлэл юм.

Загвараар хайх машин

1. Deque классыг main() функцэд

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 16: Searching for patterns in a text string

// Pattern matching algorithm

#include "deque_list.h"

//(A*B+AC)D
char ch[10] = {' ', 'A', ' ', 'B', ' ', ' ', 'A', 'C', 'D', ' '};
int next1[10] = { 5, 2, 3, 4, 8, 6, 7, 8, 9, 0};
int next2[10] = { 5, 2, 1, 4, 8, 2, 7, 8, 9, 0};

/*
// ca*b
char ch[5] = {'c', ' ', 'a', 'b', ' '};
int next1[5] = {1,2,1,4,0};
int next2[5] = {1,3,1,4,0};
*/

const int scan = -1;

int patternmatch(char *text) {
  Deque<int> dq;
  int n1, n2;
  int j = 0, n = strlen(text), state = next1[0];
  dq.insert(scan);
  while (state) {
    if (state == scan) {
      j++; dq.insert(scan);
      state = next1[0]; continue;
    }
    else if (ch[state] == text[j])
      dq.insert(next1[state]);
    else if (ch[state] == ' ') {
      n1 = next1[state]; n2 = next2[state];
      dq.push(n1); if (n1 != n2) dq.push(n2);
    }
    if (dq.empty() || j==n) return 0;
    dq.pop(state);
  }
  return j;
}

int main() {
  char text[80];
  cout << "search pattern: (A*B+AC)D\n";
  cout << "input text in CAPITAL letter: ";
  gets(text);
  strcat(text,".");
  cout << patternmatch(text) << endl;
}

2. Толгой файл: deque_list.h

// Data Structure & Algorithm C++, Otgonbayar Tovuudorj
// Chapter 16: Searching for patterns in a text string


// Deque class - Double-ended queue
// File name: deque_list.h

#include <iostream>
#include <iomanip>
#include <string.h>

using namespace std;

//enum bool {false, true};

template <class Type>
class Deque {
  struct Node {
    Type data; Node *link;
    Node(Type d, Node *pt=NULL) : data(d), link(pt) {}
  };
  Node *top, *back;
public:
  Deque() {
    top = back = NULL;
  }
  ~Deque();
  bool insert(Type item);
  bool push(Type item);
  bool pop(Type& item);
  bool empty();
};

template<class Type>
Deque<Type>::~Deque() {
  Node *temp;
  while (top) {
    temp = top; top = top->link;
    delete temp;
  }
}

template<class Type>
bool Deque<Type>::pop(Type& item) {
  if(empty()) {
    cout << "Stack is empty" << endl;
    return false;
  }
  else {
    Node *temp = top;
    item = top->data;
    if(back == top) back = NULL;
    top = top->link;
    delete temp;
    return true;
  }
}

template<class Type>
bool Deque<Type>::push(Type item) {
  Node *new_node = new Node(item, top);
  if(new_node) {
    top = new_node;
    if(!back) back = top;
    return true;
  }
  else return false;
}

template <class Type>
bool Deque<Type>::insert(Type item) {
  Node *new_node = new Node(item);
  if(new_node) {
    if(empty()) top = back = new_node;
    else {
      back->link = new_node;
      back = back->link;
    }
    return true;
  }
  else return false;
}

template <class Type>
bool Deque<Type>::empty() {
   if(!top) return true;
   else return false;
}