package class_2023_02_4_week;

import java.util.ArrayList;
import java.util.Arrays;

// 你想要用小写字母组成一个目标字符串 target。 
// 开始的时候，序列由 target.length 个 '?' 记号组成
// 而你有一个小写字母印章 stamp。
// 在每个回合，你可以将印章放在序列上，并将序列中的每个字母替换为印章上的相应字母
// 你最多可以进行 10 * target.length  个回合
// 举个例子，如果初始序列为 "?????"，而你的印章 stamp 是 "abc"
// 那么在第一回合，你可以得到 "abc??"、"?abc?"、"??abc"
//（请注意，印章必须完全包含在序列的边界内才能盖下去。）
// 如果可以印出序列，那么返回一个数组，该数组由每个回合中被印下的最左边字母的索引组成
// 如果不能印出序列，就返回一个空数组。
// 例如，如果序列是 "ababc"，印章是 "abc"
// 那么我们就可以返回与操作 "?????" -> "abc??" -> "ababc" 相对应的答案 [0, 2]
// 另外，如果可以印出序列，那么需要保证可以在 10 * target.length 个回合内完成
// 任何超过此数字的答案将不被接受
// 测试链接 : https://leetcode.cn/problems/stamping-the-sequence/
public class Code04_StampingTheSequence {

	public static int[] movesToStamp(String stamp, String target) {
		char[] s = stamp.toCharArray();
		char[] t = target.toCharArray();
		int m = s.length;
		int n = t.length;
		int[] inDegrees = new int[n - m + 1];
		// 所有在target里开头的字符串，认为和stamp，每个位置都不一样
		Arrays.fill(inDegrees, m);
		ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			graph.add(new ArrayList<>());
		}
		// 入度为0的开头，进入到queue里
		int[] queue = new int[n - m + 1];
		int l = 0;
		int r = 0;
		for (int i = 0; i <= n - m; i++) {
			// i....撸m个字符
			for (int j = 0; j < m; j++) {
				if (t[i + j] == s[j]) {
					if (--inDegrees[i] == 0) {
						queue[r++] = i;
					}
				} else {
					graph.get(i + j).add(i);
				}
			}
		}
		// visited[17] == true
		boolean[] visited = new boolean[n];
		int[] path = new int[n - m + 1];
		int size = 0;
		while (l < r) {
			// cur位置开头的字符串，弹出了！入度为0！恭喜啊！！！！
			int cur = queue[l++];
			path[size++] = cur;
			for (int i = 0; i < m; i++) {
				if (!visited[cur + i]) {
					visited[cur + i] = true;
					for (int next : graph.get(cur + i)) {
						if (--inDegrees[next] == 0) {
							queue[r++] = next;
						}
					}
				}
			}
		}
		if (size != n - m + 1) {
			return new int[0];
		}
		// path里
		for (int i = 0, j = size - 1; i < j; i++, j--) {
			int tmp = path[i];
			path[i] = path[j];
			path[j] = tmp;
		}
		return path;
	}

}