In this paper, we propose an efficient dedicated tool for searching the best differential and linear trails of bit-permutation-based ciphers. The key innovation of our approach lies in integrating a divide-and-conquer strategy into Matsui’s search algorithm. To accomplish this correctly and efficiently, we propose two novel methods: the first divides the search space in a way adapted to Matsui’s algorithm, and the second uses fine-grained variables to give a tighter lower bound estimate on the weight of each subset. For word-wise Feistel-like (also bit-permutation-based) ciphers, such as LBlock, TWINE and WARP, we further enhance the efficiency of the tool by proposing two new strategies: one that exploits the structure of the linear layer to speed up the pruning and another that employs memoization to avoid redundant computations. The superiority of our tool is demonstrated by obtaining the best differential and linear trails for full rounds of RECTANGLE, KNOT permutations, PRESENT, GIFT, LBlock, TWINE, and WARP. Last but not least, based on our dedicated tool and a novel memoization strategy, we further investigate the clustering of differential trails for KNOT, PRESENT and WARP: for KNOT, we investigate differential trail clustering of the 52, 76 and 100 rounds identified for KNOT-256, KNOT-384 and KNOT-512 respectively; for PRESENT, we investigate a known 14-round differential distinguisher; for WARP, we investigate a known 18-round differential distinguisher. As a result, we derive more accurate estimates of probabilities of all the mentioned differential distinguishers, which can be used to better evaluate the security redundancy or mount improved attacks on the three ciphers.