01串划分(C++/Py/Java /Js/Go)题解

京东技术岗 0314笔试 第二题

题目内容

小钟有一个长度为 $n$ 的 $01$ 串 $s$ (仅由字符 $0$ 和 $1$ 组成，如 $0101101$ )，还有 $m$ 个数字 $a_1,a_2,...,a_m$ 。
他想知道：是否能选择 $m$ 个不相交的区间 $[l_1,r_1],[l_2,r_2],...,[l_m,r_m]$，使得每个数字 $a_i$ 的二进制表示(无前置$0$ , $0$ 的二进制就是 "$0$ ")，都能被 $s$ 中对应的连续子串 $s[l_i..r_i]$ 精确表示。

输入描述

输入包括多组测试数据。
1.第一行包括一个正整数 $T(1\le T\le 20)$,表示测试数据组数。
2.每组测试数据：

• 第一行有两个整数 $n(1\le n\le 100),m(1\le m\le 6)$，分别表示 $01$ 串 $s$ 的长度和数字个数。
• 第二行有一行长度为 $n$ 的 $01$ 串 $s$ 。
• 第三行有 $m$ 个整数 $a_1,a_2,...a_m(0\le a_i<2^{10})$,表示待匹配的数字。

输出描述

对于每组测试数据，输出一行:

• 若存在满足条件的 $m$ 个不相交区间，输出 $YES$
• 否则输出 $NO$

样例1

输入

2
5 2
10110
2 1
5 1
00000
1

输出

YES
NO

说明
对于第一组测试数据，$2$ 的二进制表示为 $10$，$1$ 的二进制表示为 $1$ ，其中一种可以选择的区间 为 $[1,2]、[3,3]$。
对于第二组测试数据，$1$ 的二进制表示为 $1$，由于 $01$ 串中不存在字符 $1$，故答案一定不存在。

思路

状态DP + KMP

1. 将每组输入的数字转换为二进制字符串
2. 使用kmp算法预处理每个数字二进制在s中存在的所有位置。
3. 由于m比较小，可以使用状态dp枚举进行求解，dp[mask]表示的含义为选择mask二进制为1位置的数之后，右端点的最小值.
4. 初始设置dp[0] = -1，其它设置一个认为不可达值, 枚举mask为[1, 2^m-1], 状态转移过程为
   1. 假设mask不可达直接跳过，无法进行状态转移
   2. 尝试选择当前mask未选择的数i，考虑加入i，枚举i在s中所有位置区间[l,r]
      • 如果dp[mask] < l肯定不会发生重叠，更新dp[maks | 1 << i] = min(dp[maks | 1 << i], y)
      • 大于等于说明会发生冲突
5. 最后判断2^m -1是否可达即可

C++

#include<bits/stdc++.h>
using namespace std;


string intToStr(int x) {
    if (x == 0) {
        return "0";
    }
    string s;
    while (x > 0) {
        s += (x % 2) ? "1" : "0";
        x /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}

bool solve(int n, int m, string s,vector<int>& a) {
    // 将数组转换为二进制字符串
    vector<string> nums(m);
    for (int i = 0; i < m; i++) {
        int val = a[i];
        nums[i] = intToStr(val);
    }
    // 记录每个数再s中匹配的位置
    vector<vector<pair<int,int>>> index(m);
    int k = 0;
    // 使用kmp加快匹配
    for (string num : nums) {
        int len = num.size();
        vector<int> pi(len);
        for (int i = 1, j = 0; i < len; i++) {
            while (j && num[j] != num[i]) {
                j = pi[j - 1];
            }
            if (num[i] == num[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < s.size(); i++) {
            while (j && s[i] != num[j]) {
                j = pi[j-1];
            }
            if (s[i] == num[j]) {
                j++;
            }
            if (j == len) {
                int l = i - len + 1;
                index[k].push_back({l, i});
                j = pi[j-1];
            }
        }
        k++;
    }
    
    vector<int> dp(1 << m, INT_MAX);
    dp[0] = -1;
    for (int mask = 0; mask < (1 << m); mask++) {
        if (dp[mask] == INT_MAX) {
            continue;
        }
        for (int i = 0; i < m; i++) {
            // 已经被处理
            if (mask & 1 << i) {
                continue;
            }
            for (auto [x, y] : index[i]) {
                if (dp[mask] < x) {
                    dp[mask | (1<<i)] = min(dp[mask | (1<<i)], y);
                }
            }
        }
    }
    return dp[(1<<m)-1]!=INT_MAX;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        string s;
        cin >> s;
        vector<int> a(m);
        for (int i = 0; i < m; i++) {
            cin >> a[i];
        }
        
        bool flag =  solve(n, m, s, a);
        if (flag) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
}

java

import java.io.*;
import java.util.*;

public class Main {

    static String intToStr(int x) {
        if (x == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        while (x > 0) {
            sb.append((x % 2) == 1 ? '1' : '0');
            x /= 2;
        }
        return sb.reverse().toString();
    }

    static boolean solve(int n, int m, String s, int[] a) {
        // 将数组转换为二进制字符串
        String[] nums = new String[m];
        for (int i = 0; i < m; i++) {
            nums[i] = intToStr(a[i]);
        }

        // 记录每个数在s中匹配的位置
        List<List<int[]>> index = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            index.add(new ArrayList<>());
        }

        int k = 0;

        // 使用KMP加快匹配
        for (String num : nums) {
            int len = num.length();
            int[] pi = new int[len];

            for (int i = 1, j = 0; i < len; i++) {
                while (j > 0 && num.charAt(j) != num.charAt(i)) {
                    j = pi[j - 1];
                }
                if (num.charAt(i) == num.charAt(j)) {
                    j++;
                }
                pi[i] = j;
            }

            for (int i = 0, j = 0; i < s.length(); i++) {
                while (j > 0 && s.charAt(i) != num.charAt(j)) {
                    j = pi[j - 1];
                }
                if (s.charAt(i) == num.charAt(j)) {
                    j++;
                }
                if (j == len) {
                    int l = i - len + 1;
                    index.get(k).add(new int[]{l, i});
                    j = pi[j - 1];
                }
            }

            k++;
        }

        int[] dp = new int[1 << m];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = -1;

        for (int mask = 0; mask < (1 << m); mask++) {
            if (dp[mask] == Integer.MAX_VALUE) {
                continue;
            }

            for (int i = 0; i < m; i++) {
                // 已经被处理
                if ((mask & (1 << i)) != 0) {
                    continue;
                }

                for (int[] p : index.get(i)) {
                    int x = p[0];
                    int y = p[1];
                    if (dp[mask] < x) {
                        dp[mask | (1 << i)] = Math.min(dp[mask | (1 << i)], y);
                    }
                }
            }
        }

        return dp[(1 << m) - 1] != Integer.MAX_VALUE;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

        while (T-- > 0) {

            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());

            String s = br.readLine();

            st = new StringTokenizer(br.readLine());
            int[] a = new int[m];
            for (int i = 0; i < m; i++) {
                a[i] = Integer.parseInt(st.nextToken());
            }

            boolean flag = solve(n, m, s, a);

            if (flag) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }
    }
}

python

import sys


def intToStr(x):
    if x == 0:
        return "0"
    s = []
    while x > 0:
        s.append('1' if x % 2 else '0')
        x //= 2
    return ''.join(reversed(s))


def solve(n, m, s, a):
    # 将数组转换为二进制字符串
    nums = [intToStr(x) for x in a]

    # 记录每个数在s中匹配的位置
    index = [[] for _ in range(m)]

    k = 0

    # 使用KMP加快匹配
    for num in nums:
        length = len(num)
        pi = [0] * length

        j = 0
        for i in range(1, length):
            while j and num[j] != num[i]:
                j = pi[j - 1]
            if num[i] == num[j]:
                j += 1
            pi[i] = j

        j = 0
        for i in range(len(s)):
            while j and s[i] != num[j]:
                j = pi[j - 1]
            if s[i] == num[j]:
                j += 1
            if j == length:
                l = i - length + 1
                index[k].append((l, i))
                j = pi[j - 1]

        k += 1

    dp = [2 ** 31 - 1] * (1 << m)
    dp[0] = -1

    for mask in range(1 << m):
        if dp[mask] == 2 ** 31 - 1:
            continue

        for i in range(m):
            # 已经被处理
            if mask & (1 << i):
                continue

            for x, y in index[i]:
                if dp[mask] < x:
                    nxt = mask | (1 << i)
                    dp[nxt] = min(dp[nxt], y)

    return dp[(1 << m) - 1] != 2 ** 31 - 1


def main():
    input = sys.stdin.readline

    T = int(input())

    for _ in range(T):
        n, m = map(int, input().split())
        s = input().strip()
        a = list(map(int, input().split()))

        flag = solve(n, m, s, a)

        if flag:
            print("YES")
        else:
            print("NO")


if __name__ == "__main__":
    main()

javascript

const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

const input = [];

rl.on("line", (line) => {
    input.push(line);
});

rl.on("close", () => {
    let idx = 0;

    function next() {
        return input[idx++];
    }

    function intToStr(x) {
        if (x === 0) {
            return "0";
        }
        let s = [];
        while (x > 0) {
            s.push((x % 2) ? '1' : '0');
            x = Math.floor(x / 2);
        }
        s.reverse();
        return s.join('');
    }

    function solve(n, m, s, a) {
        // 将数组转换为二进制字符串
        const nums = new Array(m);
        for (let i = 0; i < m; i++) {
            nums[i] = intToStr(a[i]);
        }

        // 记录每个数在s中匹配的位置
        const index = Array.from({ length: m }, () => []);

        let k = 0;

        // 使用KMP加快匹配
        for (const num of nums) {
            const len = num.length;
            const pi = new Array(len).fill(0);

            for (let i = 1, j = 0; i < len; i++) {
                while (j && num[j] !== num[i]) {
                    j = pi[j - 1];
                }
                if (num[i] === num[j]) {
                    j++;
                }
                pi[i] = j;
            }

            for (let i = 0, j = 0; i < s.length; i++) {
                while (j && s[i] !== num[j]) {
                    j = pi[j - 1];
                }
                if (s[i] === num[j]) {
                    j++;
                }
                if (j === len) {
                    const l = i - len + 1;
                    index[k].push([l, i]);
                    j = pi[j - 1];
                }
            }

            k++;
        }

        const INF = 0x7fffffff;
        const dp = new Array(1 << m).fill(INF);
        dp[0] = -1;

        for (let mask = 0; mask < (1 << m); mask++) {
            if (dp[mask] === INF) {
                continue;
            }

            for (let i = 0; i < m; i++) {
                // 已经被处理
                if (mask & (1 << i)) {
                    continue;
                }

                for (const [x, y] of index[i]) {
                    if (dp[mask] < x) {
                        const nxt = mask | (1 << i);
                        dp[nxt] = Math.min(dp[nxt], y);
                    }
                }
            }
        }

        return dp[(1 << m) - 1] !== INF;
    }

    const T = Number(next());

    const ans = [];

    for (let t = 0; t < T; t++) {
        const [n, m] = next().split(' ').map(Number);

        const s = next();

        const a = next().split(' ').map(Number);

        const flag = solve(n, m, s, a);

        if (flag) {
            ans.push("YES");
        } else {
            ans.push("NO");
        }
    }

    console.log(ans.join('\n'));
});

Go

package main

import (
	"bufio"
	"fmt"
	"os"
)

type Pair struct {
	x int
	y int
}

func intToStr(x int) string {
	if x == 0 {
		return "0"
	}

	bytes := make([]byte, 0)
	for x > 0 {
		if x%2 == 1 {
			bytes = append(bytes, '1')
		} else {
			bytes = append(bytes, '0')
		}
		x /= 2
	}

	// 反转
	for i, j := 0, len(bytes)-1; i < j; i, j = i+1, j-1 {
		bytes[i], bytes[j] = bytes[j], bytes[i]
	}

	return string(bytes)
}

func solve(n int, m int, s string, a []int) bool {
	// 将数组转换为二进制字符串
	nums := make([]string, m)
	for i := 0; i < m; i++ {
		nums[i] = intToStr(a[i])
	}

	// 记录每个数在s中匹配的位置
	index := make([][]Pair, m)

	k := 0

	// 使用KMP加快匹配
	for _, num := range nums {
		length := len(num)
		pi := make([]int, length)

		for i, j := 1, 0; i < length; i++ {
			for j > 0 && num[j] != num[i] {
				j = pi[j-1]
			}
			if num[i] == num[j] {
				j++
			}
			pi[i] = j
		}

		for i, j := 0, 0; i < len(s); i++ {
			for j > 0 && s[i] != num[j] {
				j = pi[j-1]
			}
			if s[i] == num[j] {
				j++
			}
			if j == length {
				l := i - length + 1
				index[k] = append(index[k], Pair{l, i})
				j = pi[j-1]
			}
		}

		k++
	}

	const INF = int(^uint(0) >> 1)

	dp := make([]int, 1<<m)
	for i := range dp {
		dp[i] = INF
	}
	dp[0] = -1

	for mask := 0; mask < (1 << m); mask++ {
		if dp[mask] == INF {
			continue
		}

		for i := 0; i < m; i++ {
			// 已经被处理
			if (mask & (1 << i)) != 0 {
				continue
			}

			for _, p := range index[i] {
				x := p.x
				y := p.y
				if dp[mask] < x {
					nxt := mask | (1 << i)
					if y < dp[nxt] {
						dp[nxt] = y
					}
				}
			}
		}
	}

	return dp[(1<<m)-1] != INF
}

func main() {
	in := bufio.NewReader(os.Stdin)

	var T int
	fmt.Fscan(in, &T)

	for ; T > 0; T-- {
		var n, m int
		fmt.Fscan(in, &n, &m)

		var s string
		fmt.Fscan(in, &s)

		a := make([]int, m)
		for i := 0; i < m; i++ {
			fmt.Fscan(in, &a[i])
		}

		flag := solve(n, m, s, a)

		if flag {
			fmt.Println("YES")
		} else {
			fmt.Println("NO")
		}
	}
}