← Home
```go
package main

import "fmt"

func main() {
	var c, s, t string
	fmt.Scan(&c)
	fmt.Scan(&s)
	fmt.Scan(&t)

	n := len(c)
	ms := len(s)
	mt := len(t)

	// Compute pi for s
	pi_s := make([]int, ms)
	j := 0
	for i := 1; i < ms; i++ {
		for j > 0 && s[i] != s[j] {
			j = pi_s[j-1]
		}
		if s[i] == s[j] {
			j++
		}
		pi_s[i] = j
	}

	// Compute next_state and match_count for s
	next_s := make([][]int, ms)
	match_s := make([][]int, ms)
	for i := 0; i < ms; i++ {
		next_s[i] = make([]int, 26)
		match_s[i] = make([]int, 26)
	}
	for state := 0; state < ms; state++ {
		for ch := 0; ch < 26; ch++ {
			temp := state
			for temp > 0 && ch != int(s[temp]-'a') {
				temp = pi_s[temp-1]
			}
			if ch == int(s[temp]-'a') {
				temp++
			}
			delta := 0
			if temp == ms {
				delta = 1
				temp = pi_s[ms-1]
			}
			next_s[state][ch] = temp
			match_s[state][ch] = delta
		}
	}

	// Compute pi for t
	pi_t := make([]int, mt)
	j = 0
	for i := 1; i < mt; i++ {
		for j > 0 && t[i] != t[j] {
			j = pi_t[j-1]
		}
		if t[i] == t[j] {
			j++
		}
		pi_t[i] = j
	}

	// Compute next_state and match_count for t
	next_t := make([][]int, mt)
	match_t := make([][]int, mt)
	for i := 0; i < mt; i++ {
		next_t[i] = make([]int, 26)
		match_t[i] = make([]int, 26)
	}
	for state := 0; state < mt; state++ {
		for ch := 0; ch < 26; ch++ {
			temp := state
			for temp > 0 && ch != int(t[temp]-'a') {
				temp = pi_t[temp-1]
			}
			if ch == int(t[temp]-'a') {
				temp++
			}
			delta := 0
			if temp == mt {
				delta = 1
				temp = pi_t[mt-1]
			}
			next_t[state][ch] = temp
			match_t[state][ch] = delta
		}
	}

	// DP
	const INF = 2000000
	dp := make([][][]int, n+1)
	for i := 0; i <= n; i++ {
		dp[i] = make([][]int, ms)
		for ps := 0; ps < ms; ps++ {
			dp[i][ps] = make([]int, mt)
			for pt := 0; pt < mt; pt++ {
				dp[i][ps][pt] = -INF
			}
		}
	}
	dp[0][0][0] = 0

	for pos := 0; pos < n; pos++ {
		for ps := 0; ps < ms; ps++ {
			for pt := 0; pt < mt; pt++ {
				if dp[pos][ps][pt] == -INF {
					continue
				}
				// Possible ch
				min_ch := 0
				max_ch := 25
				if c[pos] != '*' {
					ch_fixed := int(c[pos] - 'a')
					min_ch = ch_fixed
					max_ch = ch_fixed
				}
				for ch := min_ch; ch <= max_ch; ch++ {
					news := next_s[ps][ch]
					delta_s := match_s[ps][ch]
					newt := next_t[pt][ch]
					delta_t := match_t[pt][ch]
					new_score := dp[pos][ps][pt] + delta_s - delta_t
					if new_score > dp[pos+1][news][newt] {
						dp[pos+1][news][newt] = new_score
					}
				}
			}
		}
	}

	// Find max
	ans := -INF
	for ps := 0; ps < ms; ps++ {
		for pt := 0; pt < mt; pt++ {
			if dp[n][ps][pt] > ans {
				ans = dp[n][ps][pt]
			}
		}
	}
	fmt.Println(ans)
}
```