golang DP+KMP with comments
\nvar next []int\nconst mod = 1000000000 + 7\n\nfunc findGoodStrings(n int, s1 string, s2 string, evil string) int {\n\tnext = getNextArray(evil)\n\tdpMap := ma
```\nvar next []int\nconst mod = 1000000000 + 7\n\nfunc findGoodStrings(n int, s1 string, s2 string, evil string) int {\n\tnext = getNextArray(evil)\n\tdpMap := map[int]map[int]map[bool]map[bool]int{}\n\treturn f(s1, s2, evil, 0, 0, true, true, dpMap)\n}\n\n// f(s1,s2,k,pos,evilCount,meetS1,meetS2) return number of good elem\n// param: pos: position to be filled\n//\t\t\tevilCount: how many digit in evil has been meet\n//\t\t\tmeetS1: if > s1\n//\t\t\tmeetS2: if < s2\n// f(i,evilCount,meetS1,meetS2)->add->sum(lowerBound to upperBound) f(i+1,evilCount,meetS1,meetS2)\n//\t \tlowerBound = \'a\', upperBound = \'z\'\n//\t\tif !meetS1, lowerBound=s1[i]\n// \t\tif !meetS2, upperBound=s2[i]\n//\t\tfrom elem = lowerBound->upperBound, if elem>lowerBound, set meetS1. if elem<upperBound, set meetS2\n// \t\tif elem still in the evil string, evilCount++\n// init state\n//\t\tf(n,evilCount=0->k,0/1,0/1)=upperBound-lowerBound\n\nfunc f(s1, s2, evil string, pos, evilCount int, meetS1, meetS2 bool, dp map[int]map[int]map[bool]map[bool]int) int {\n\t//init map\n\tif dp[pos] == nil {\n\t\tdp[pos] = map[int]map[bool]map[bool]int{}\n\t}\n\tif dp[pos][evilCount] == nil {\n\t\tdp[pos][evilCount] = map[bool]map[bool]int{}\n\t}\n\tif dp[pos][evilCount][meetS1] == nil {\n\t\tdp[pos][evilCount][meetS1] = map[bool]int{}\n\t}\n\n\t// ========== if exist, just return ==============\n\tif v, exist := dp[pos][evilCount][meetS1][meetS2]; exist {\n\t\treturn v\n\t}\n\n\t// =========== not exist, we start to fill the value ============\n\n\t// now pos is the last digit, we can fill init state\n\tlength := len(s1)\n\tif evilCount == len(evil) {\n\t\tdp[pos][evilCount][meetS1][meetS2] = 0\n\t\treturn 0\n\t}\n\n\t//calc boundary for sum f\n\tvar lowerBound uint8 = \'a\'\n\tvar upperBound uint8 = \'z\'\n\tif meetS1 {\n\t\tlowerBound = s1[pos]\n\t}\n\tif meetS2 {\n\t\tupperBound = s2[pos]\n\t}\n\t// non-exist boundary\n\tif upperBound < lowerBound {\n\t\tdp[pos][evilCount][meetS1][meetS2] = 0\n\t\treturn 0\n\t}\n\tif pos == length-1 {\n\t\tdp[pos][evilCount][meetS1][meetS2] = int(upperBound - lowerBound + 1)\n\t\tif evilCount == len(evil)-1 {\n\t\t\tif evil[len(evil)-1] >= lowerBound && evil[len(evil)-1] <= upperBound {\n\t\t\t\tdp[length-1][evilCount][meetS1][meetS2] = dp[length-1][evilCount][meetS1][meetS2] - 1\n\t\t\t}\n\t\t}\n\t\treturn dp[pos][evilCount][meetS1][meetS2]\n\t}\n\n\t// pos is not last digit, we need to sum all possible f(pos+1)\n\tfor i := lowerBound; i <= upperBound; i++ {\n\t\tnewMeetS1 := meetS1\n\t\tnewMeetS2 := meetS2\n\t\tif i > s1[pos] {\n\t\t\tnewMeetS1 = false\n\t\t}\n\t\tif i < s2[pos] {\n\t\t\tnewMeetS2 = false\n\t\t}\n\t\tnewEvilCount := checkEvil(i, evilCount, evil)\n\t\tdp[pos][evilCount][meetS1][meetS2] += f(s1, s2, evil, pos+1, newEvilCount, newMeetS1, newMeetS2, dp)\n        dp[pos][evilCount][meetS1][meetS2] = dp[pos][evilCount][meetS1][meetS2] % mod\n\t}\n\t\n\treturn dp[pos][evilCount][meetS1][meetS2]\n}\n\nfunc checkEvil(toBeAdded byte, evilCount int, evil string) int {\n\tfor evilCount > 0 && evil[evilCount] != toBeAdded {\n\t\tevilCount = next[evilCount-1]\n\t}\n\tif evil[evilCount] == toBeAdded {\n\t\tevilCount++\n\t}\n\treturn evilCount\n}\n\nfunc getNextArray(evil string) []int {\n\tpLen := len(evil)\n\tnext := make([]int, pLen, pLen)\n\ti := 1\n\tj := 0\n\tfor i < pLen {\n\t\tif evil[i] == evil[j] {\n\t\t\tj++\n\t\t\tnext[i] = j\n\t\t\ti++\n\t\t} else {\n\t\t\tif j != 0 {\n\t\t\t\tj = next[j-1]\n\t\t\t} else {\n\t\t\t\ti++\n\t\t\t}\n\t\t}\n\t}\n\treturn next\n}\n```
['Dynamic Programming', 'Go']