// pattern matching

#ifndef NULL
#define NULL 0
#endif

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

enum BOOL {FALSE, TRUE};
typedef int itemType;

// state machine:
//                0    1    2    3    4    5    6    7    8    9
//---------------------------------------------------------------
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 };


class i {
	private:
		itemType a;
	public:
		i()                              // default constructor
			{ a = 0; next = NULL; }
		i(itemType c)							// parametric constructor
			{ a = c; next = NULL; }
		i * next;
		itemType getVal()
			{ return a; }
};

class Deque { // output-restricted double-ended queue
	// You can both push and put objects into the deque. Objects put in the
	// deque are inserted after the last object, objects pushed are inserted
	// in front of the first. When you pop, you get the first object in the
	// deque. The method emtpy() returns TRUE (1) if the deque is empty,
	// FALSE (0) otherwise.
	private:
		i * head;
		i * z;
	public:
		Deque() {
			head = new i(); z = new i();
			head->next = z; z->next = z;
		}
		~Deque();
		itemType pop();
		void push(itemType c);
		void put(itemType c);
		BOOL empty()
			{ return (BOOL)(head->next==z); }
};

void Deque::push(itemType c) {
	i * temp = new i(c);
	temp->next = head->next;
	head->next = temp;
}

void Deque::put(itemType c) {
	i * temp = new i(c);
	temp->next = z;
	i * t2   = head;
	while (t2->next!=z)
		t2=t2->next;
	t2->next=temp;
}

itemType Deque::pop() {
	itemType x;
	i * temp = head->next;
	head->next = temp->next;
	x = temp->getVal();
	delete temp; return x;
}

Deque::~Deque() {
	i * temp = head;
	while (temp != z)
		{ head = temp; temp=temp->next; delete head; }
}

const int scan = -1;

int match(char *a) {
	int n1, n2; Deque dq;
	int j = 0, N = strlen(a), state = next1[0];
	dq.put(scan);
	while (state) {
		if (state == scan) { j++; dq.put(scan); }
		else if (ch[state] == a[j])
			dq.put(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;
		state = dq.pop();
	}
	return j;
}

void main() {
	char *a="SUDAABDDUB";
	cout << match(a);
}