from abc import abstractmethod

class Token:

	is_skippable = False

	@abstractmethod

	def list_first(self):

		pass

	@abstractmethod

	def list_last(self):

		pass

	@abstractmethod

	def list_neighbours(self):

		pass

class Symbol(Token):

	def __init__(self, position, value):

		self.position = position

		self.value = value

	def list_first(self):

		yield self.position

	def list_last(self):

		yield self.position

	def list_neighbours(self):

		yield from []

	def __str__(self):

		return self.value

class Plus(Token):

	def __init__(self, content: Token):

		self.content = content

	def list_first(self):

		yield from self.content.list_first()

	def list_last(self):

		yield from self.content.list_last()

	def list_neighbours(self):

		yield from self.content.list_neighbours()

		for x in self.list_last():

			for y in self.list_first():

				yield (x, y)

	def __str__(self):

		return str(self.content) + "+"

class Asterisk(Plus):

	is_skippable = True

	def __str__(self):

		return str(self.content) + "*"

class Chain(Token):

	def __init__(self, content: list):

		self.content = content

	def list_first(self):

		for token in self.content:

			yield from token.list_first()

			if not token.is_skippable:

				break

	def list_last(self):

		for token in reversed(self.content):

			yield from token.list_last()

			if not token.is_skippable:

				break

	def list_neighbours(self):

		previous = []

		for token in self.content:

			for t in previous:

				for x in t.list_last():

					for y in token.list_first():

						yield (x, y)

			yield from token.list_neighbours()

			if token.is_skippable:

				previous.append(token)

			else:

				previous = [token]

	def __str__(self):

		return "(" + "".join(str(x) for x in self.content) + ")"

def find_closing_parenthesis(pattern, k):

	counter = 0

	for (i, c) in enumerate(pattern[k:]):

		if c == "(":

			counter += 1

		elif c == ")":

			counter -= 1

		if counter == 0:

			return k+i

	return None

def parse(pattern, offset=0):

	res = []

	i = 0

	while i < len(pattern):

		c = pattern[i]

		if c == "(":

			j = find_closing_parenthesis(pattern, i)

			inner_content = parse(pattern[i+1:j], offset+i+1)

			res.append(inner_content)

			i = j+1

		elif c == "*":

			token = res.pop()

			res.append(Asterisk(token))

			i += 1

		elif c == "+":

			token = res.pop()

			res.append(Plus(token))

			i += 1

		else:

			res.append(Symbol(i+offset, c))

			i += 1

	return Chain(res)

class Regexp:

	def __init__(self, s):

		(self.rules, self.end_states) = self._parse(s)

	def _parse(self, s):

		r = parse(s)

		rules = dict()

		for i in r.list_first():

			c = s[i]

			key = (-1, c)

			if key not in rules:

				rules[key] = set()

			rules[key].add(i)

		for (i, j) in r.list_neighbours():

			c = s[j]

			key = (i, c)

			if key not in rules:

				rules[key] = set()

			rules[key].add(j)

		end_states = set(r.list_last())

		return rules, end_states

	def match(self, s):

		current = {-1}

		for c in s:

			new_state = set()

			for st in current:

				key = (st, c)

				if key in self.rules:

					new_state.update(self.rules[key])

			current = new_state

		return any(st in self.end_states for st in current)

if __name__ == "__main__":

	for pattern in ["a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"]:

		print("#", pattern)

		r = Regexp(pattern)

		for t in tests:

			print(t, r.match(t))

		print()

use std::collections::{HashMap, HashSet};

const START: usize = usize::MAX;

trait Token {

	fn is_skippable(&self) -> bool {false}

	fn list_first(&self) -> Vec<usize>;

	fn list_last(&self) -> Vec<usize>;

	fn list_neighbours(&self) -> Vec<(usize, usize)>;

}

struct Symbol {

	position: usize,

	value: char

}

struct Asterisk {

	content: Box<dyn Token>

}

struct Plus {

	content: Box<dyn Token>

}

struct Chain {

	content: Vec<Box<dyn Token>>

}

impl Token for Symbol {

	fn list_first(&self) -> Vec<usize> {

		return vec![self.position];

	}

	fn list_last(&self) -> Vec<usize> {

		return vec![self.position];

	}

	fn list_neighbours(&self) -> Vec<(usize, usize)> {

		return vec![];

	}

}

impl Token for Asterisk {

	fn is_skippable(&self) -> bool {true}

	fn list_first(&self) -> Vec<usize> {

		return self.content.list_first();

	}

	fn list_last(&self) -> Vec<usize> {

		return self.content.list_last();

	}

	fn list_neighbours(&self) -> Vec<(usize, usize)> {

		let mut res = self.content.list_neighbours();

		for x in self.list_last() {

			for y in self.list_first() {

				res.push((x, y));

			}

		}

		return res;

	}

}

impl Token for Plus {

	fn list_first(&self) -> Vec<usize> {

		return self.content.list_first();

	}

	fn list_last(&self) -> Vec<usize> {

		return self.content.list_last();

	}

	fn list_neighbours(&self) -> Vec<(usize, usize)> {

		let mut res = self.content.list_neighbours();

		for x in self.list_last() {

			for y in self.list_first() {

				res.push((x, y));

			}

		}

		return res;

	}

}

impl Token for Chain {

	fn list_first(&self) -> Vec<usize> {

		let mut res = Vec::new();

		for token in self.content.iter() {

			res.append(&mut token.list_first());

			if !token.is_skippable() {break;}

		}

		return res;

	}

	fn list_last(&self) -> Vec<usize> {

		let mut res = Vec::new();

		for token in self.content.iter().rev() {

			res.append(&mut token.list_last());

			if !token.is_skippable() {break;}

		}

		return res;

	}

	fn list_neighbours(&self) -> Vec<(usize, usize)> {

		let mut res = Vec::new();

		let mut previous: Vec<&Box<dyn Token>> = Vec::new();

		for token in self.content.iter() {

			for t in previous.iter() {

				for x in t.list_last() {

					for y in token.list_first() {

						res.push((x, y));

					}

				}

			}

			res.append(&mut token.list_neighbours());

			if token.is_skippable() {

				previous.push(token);

			} else {

				previous = vec![token];

			}

		}

		return res;

	}

}

fn find_closing_parenthesis(s: &String) -> Option<usize> {

	let chars: Vec<char> = s.chars().collect();

	let mut counter = 0;

	for (i, c) in chars.iter().enumerate() {

		if *c == '(' {counter += 1;}

		else if *c == ')' {counter -= 1;}

		if counter == 0 {return Some(i);}

	}

	return None;

}

fn parse(pattern: &String, offset: usize) -> Chain {

	let chars: Vec<char> = pattern.chars().collect();

	let mut res: Vec<Box<dyn Token>> = Vec::new();

	let mut i = 0;

	while i < pattern.len() {

		let c = chars[i];

		match c {

			'(' => {

				let j = find_closing_parenthesis(&pattern[i..].to_string()).unwrap() + i;

				let inner_content = parse(&pattern[i+1..j].to_string(), offset+i+1);

				res.push(Box::new(inner_content));

				i = j+1;

			}

			'*' => {

				let token = res.pop().unwrap();

				res.push(Box::new(Asterisk{content: token}));

				i += 1;

			}

			'+' => {

				let token = res.pop().unwrap();

				res.push(Box::new(Plus{content: token}));

				i += 1;

			}

			c => {

				res.push(Box::new(Symbol{position: i+offset, value: c}));

				i += 1;

			}

		}

	}

	return Chain{content: res};

}

struct Regexp {

	rules: HashMap<(usize, char), HashSet<usize>>,

	end_states: HashSet<usize>

}

impl Regexp {

	fn new(pattern: &String) -> Regexp {

		let r = parse(pattern, 0);

		let pattern_chars = Vec::from_iter(pattern.chars());

		let mut rules: HashMap<(usize, char), HashSet<usize>> = HashMap::new();

		for i in r.list_first() {

			let c = pattern_chars[i];

			let key = (START, c);

			match rules.get_mut(&key) {

				Some(set) => {set.insert(i);},

				None => {rules.insert(key, HashSet::from([i]));}

			};

		}

		for (i, j) in r.list_neighbours() {

			let c = pattern_chars[j];

			let key = (i, c);

			match rules.get_mut(&key) {

				Some(set) => {set.insert(j);},

				None => {rules.insert(key, HashSet::from([j]));}

			};

		}

		return Regexp{rules, end_states};

	}

	pub fn eval(&self, s: String) -> bool {

		let mut multistate = HashSet::from([START]);

		for c in s.chars() {

			let mut new_multistate = HashSet::new();

			for state in multistate {

				if let Some(x) = self.rules.get(&(state, c)) {

					new_multistate = new_multistate.union(&x).map(|&y| y).collect();

				} else if let Some(x) = self.rules.get(&(state, '.')) {

					new_multistate = new_multistate.union(&x).map(|&y| y).collect();

				}

			}

			multistate = new_multistate;

		}

		return multistate.iter().any(|x| self.end_states.contains(x));

	}

}

fn main() {

	for pattern in ["a*b*", "a+b+", "(ab)*", "(ab)+", "a((bc)*d)*"] {

		println!("# {pattern}");

		let r = Regexp::new(&pattern.to_string());

		for &t in tests.iter() {

			println!("{t} {}", r.eval(t.to_string()));

		}

		println!();

	}

}