# This file is automatically @generated by Cargo.

# It is not intended for manual editing.

version = 3

[[package]]

name = "regexp"

version = "0.1.0"

[package]

name = "regexp"

version = "0.1.0"

edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

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

struct Regexp {

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

	end_states: HashSet<usize>

}

impl Regexp {

	pub fn new(pattern: String) -> Self {

		println!("> {pattern}");

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

		let mut star = false;

		let mut plus = false;

		let n = pattern.len();

		let mut states = vec![HashSet::from([n])];

		let mut end_states = HashSet::new();

		let mut rules = HashMap::new();

		for i in 0..n {

			let j = n-i-1;

			let c = pattern_chars[j];

			let k = states.len()-1;

			if c == '*' {

				star = true;

				continue;

			}

			if c == '+' {

				plus = true;

				continue;

			}

			if star {

				states[k].insert(j);

				println!("{j}: {:?}", states[k]);

				Regexp::update_rule(&mut rules, j, &pattern_chars, &states[k]);

				if states[k].contains(&n) {end_states.insert(j);}

				star = false;

			}

			else if plus {

				states[k].insert(j);

				println!("{j}: {:?}", states[k]);

				Regexp::update_rule(&mut rules, j, &pattern_chars, &states[k]);

				if states[k].contains(&n) {end_states.insert(j);}

				states.push(HashSet::from([j]));

				plus = false;

			}

			else {

				println!("{j}: {:?}", states[k]);

				Regexp::update_rule(&mut rules, j, &pattern_chars, &states[k]);

				if states[k].contains(&n) {end_states.insert(j);}

				states.push(HashSet::from([j]));

			}

			if j == 0 {

				let m = states.len()-1;

				println!("99: {:?} (start)", states[m]);

				Regexp::update_rule(&mut rules, 99, &pattern_chars, &states[m]);

				if states[m].contains(&n) {end_states.insert(j);}

			}

		}

		println!("{rules:?}");

		return Regexp {rules, end_states};

	}

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

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

		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 update_rule(rules: &mut HashMap<(usize, char), HashSet<usize>>, pos: usize, pattern: &Vec<char>, values: &HashSet<usize>) {

		let n = pattern.len();

		for &target in values.iter() {

			println!("pos: {pos}, target: {target}");

			if target == n {continue;}

			let c = pattern[target];

			let key = (pos, c);

			if !rules.contains_key(&key) {rules.insert(key, HashSet::new());}

			match rules.get_mut(&key) {

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

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

			};

		}

	}

	fn find_previous_letter(s: &String, k: usize) -> Option<usize> {

		return s[..k].rfind(char::is_alphanumeric);

	}

	fn find_next_letter(s: &String, k: usize) -> Option<usize> {

		return s[k+1..].find(char::is_alphanumeric);

	}

	fn find_opening_parenthesis(s: &String, k: usize) -> Option<usize> {

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

		let mut i = k;

		let mut counter = 1;

		while counter > 0 {

			match chars[i] {

				'(' => counter -= 1,

				')' => counter += 1,

				_ => {}

			}

			match i.checked_sub(1) {

				Some(x) => i = x,

				None => return None

			}

		}

		return Some(i);

	}

}

struct Solution {}

impl Solution {

	pub fn is_match(s: String, p: String) -> bool {

		let regexp = Regexp::new(p);

		return regexp.eval(s);

	}

}

fn main() {

	// println!("{}\n", Solution::is_match(String::from("aa"), String::from("a")));

	// println!("{}\n", Solution::is_match(String::from("aa"), String::from("a*")));

	// println!("{}\n", Solution::is_match(String::from("ab"), String::from(".*")));

	// println!("{}\n", Solution::is_match(String::from("aab"), String::from("a*ab")));

	// println!("{}\n", Solution::is_match(String::from("aab"), String::from("a*b*")));

	println!("{}\n", Solution::is_match(String::from("a"), String::from("a+")));

	println!("{}\n", Solution::is_match(String::from("aa"), String::from("a+")));

	println!("{}\n", Solution::is_match(String::from(""), String::from("a+")));

	println!("{}\n", Solution::is_match(String::from("bb"), String::from("ba+b")));

	println!("{}\n", Solution::is_match(String::from("baaaaab"), String::from("ba+b")));

}