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")));
}