本文主要是介绍Kickstart Round A 2017 Problem B. Patterns Overlap，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
public static void main(String[] args) {Scanner in = new Scanner(System.in);int T = Integer.parseInt(in.nextLine());for (int t = 0; t < T; t++) {String s1 = in.nextLine();String s2 = in.nextLine();int[][] f = new int[s1.length() + 1][s2.length() + 1];// 初始状态int tpi = 0;while (tpi < s1.length() && s1.charAt(tpi) == '*') {int count = 0;for (int j = 1; j <= s2.length(); j++) {if (s2.charAt(j - 1) != '*') {count++;}f[tpi + 1][j] = 1;if (count == 4 * (tpi + 1)) {break;}}tpi++;}int tpj = 0;if (tpj < s2.length() && s2.charAt(tpj) == '*') {int count = 0;for (int i = 1; i <= s1.length(); i++) {if (s1.charAt(i - 1) != '*') {count++;}f[i][tpj + 1] = 1;if (count == 4 * (tpj + 1)) {break;}}tpj++;}if (tpi < s1.length() && tpj < s2.length() && s1.charAt(tpi) == s2.charAt(tpj)) {f[tpi + 1][tpj + 1] = 1;}for (int i = 1; i <= s1.length(); i++) {for (int j = 1; j <= s2.length(); j++) {if (f[i][j] == 1) {if ((i < s1.length()) && (s1.charAt(i) == '*')) {f[i + 1][j] = 1;int count = 0;for (int k = j; k < s2.length(); k++) {if (s2.charAt(k) != '*') {count++;}f[i + 1][k + 1] = 1;if (count == 4) {break;}}}if ((j < s2.length()) && (s2.charAt(j) == '*')) {f[i][j + 1] = 1;int count = 0;for (int k = i; k < s1.length(); k++) {if (s1.charAt(k) != '*') {count++;}f[k + 1][j + 1] = 1;if (count == 4) {break;}}}if ((i < s1.length() && j < s2.length()) && (s1.charAt(i) == s2.charAt(j))) {f[i + 1][j + 1] = 1;}}}}if (f[s1.length()][s2.length()] == 1) {System.out.println("Case #" + (t + 1) + ": TRUE");} else {System.out.println("Case #" + (t + 1) + ": FALSE");}}}
f[i][j] 表示s1前i个字符和s2前j个字符能否匹配
状态转移方程：
当f[i][j]==1时：
若s1的第i+1( s.charAt(i) )个字符为 * ，
则 f[i+1][j]=1 ( * 匹配0个字符)
f[i+1][k]=1 k从j+1到第四个非*的字符为止
若s2的第j+1个字符为*，同上。
若s1的第i+1个字符等于s2的j+1个字符，f[i+1][j+1]=1
初始状态：
若s1和s2最开始的非*字符可以互相匹配，则f[i][j]=1
这篇关于Kickstart Round A 2017 Problem B. Patterns Overlap的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
