两个字符串之间串差 [英] substring difference between two strings

问题描述

给定两个长度为n的串，P = P1 ...的pn及Q = Q1 ... QN，我们定义M（I，J，K），为圆周率之间... PI +失配数的k 1和qj..qj + k-1个。即在集表示法中，M（I，J，K）指的是一组 {0℃的大小; = X＆其中; K | PI + X不等于QJ + X | } 。

Given two strings of length n,P = p1...pn and Q = q1...qn, we define M(i, j, k) as the number of mismatches between pi...pi+k-1 and qj..qj+k-1. That is in set notation, M(i, j, k) refers to the size of the set { 0<=x<k | pi+x not equal to qj+x| }.

给定一个整数K，你的任务是找到最大长度L，使得存在对指数（I，J）对我们有 M（I，J，L）和LT =氏/ code>。当然，我们也应该有 1 + L-1＆LT; = N 和 J + L-1＆LT; = N 。 输入

Given an integer K, your task is to find the maximum length L such that there exists pair of indices (i,j) for which we have M(i, j, L) <= K. Of course, we should also have i+L-1 <=n and j+L-1 <=n. Input

输入的第一行包含一个整数T（1＆LT; = T＆LT; = 10）。 T检验案例可循。 每个测试用例由一个整数K和两个字符串P和Q用一个空格隔开。 输出

First line of input contains a single integer T (1 <=T <=10). T test cases follow. Each test case consists of an integer K and two strings P and Q separated by a single space. Output

有关每个测试用例输出一个整数L的作为最大值，从而存在对指数（I，J），使得M（I，J，L）所述的; = K

For each test case output a single integer L which is the maximum value for which there exists pair of indices (i,j) such that M(i, j, L) <=K.

限制

0℃= K＆其中; =长度的串P的 这两个P＆放大器; Q将具有相同的长度 每个字符串的大小将是在最高1500 在P＆功放的所有字符; Q为小写英文字母。

0 <= K <= length of the string P Both P & Q would have the same length The size of each of the string would be at the max 1500 All characters in P & Q are lower-case English letters.

采样输入

3
2 tabriz torino
0 abacba abcaba
3 helloworld yellomarin

示例输出

4
3
8 

说明：   第一个测试情况：如果我们把从第一字符串布里斯，和从第二串奥林，这两个串之间的错配则数目等于2，并且这些子串的长度是4。这是我们选择I = 3，J = 2，L = 4，且我们有M（3,2,4）= 2。

Explanation: First test-case: If we take "briz" from the first string, and "orin" from the second string, then the number of mismatches between these two substrings is equal to 2, and the length of these substrings are 4. That's we have chosen i=3, j=2, L=4, and we have M(3,2,4) = 2.

二测情况：由于k = 0，我们应该找到最长公共子给定输入字符串。我们可以选择ABA作为结果，我们没有两个字符串之间不再普通子。所以，答案是3本试验例。这就是我们选择I = 1，J = 4，L = 3，我们有M（1,4,3）= 0。

Second test-case: Since K=0, we should find the longest common substring for the given input strings. We can choose "aba" as the result, and we don't have longer common substring between two strings. So, the answer is 3 for this test-case. That's we have chosen i=1, j=4, and L=3, and we have M(1,4,3)=0.

第三个测试案例：我们可以选择在第二个字符串的第一个字符串和yellomarhellowor。所以，我们选择了I = 1，J = 1，并且L = 8，而且我们有M（1,1,8）= 3。当然我们也可以选择我= 2，J = 2，L = 8，我们仍然有M（2,2,8）= 3。

Third test-case: We can choose "hellowor" from first string and "yellomar" from the second string. So, we have chosen i=1, j=1, and L=8, and we have M(1,1,8)=3. Of course we can also choose i=2, j=2, and L=8 and we still have M(2,2,8)=3.

这是我的执行

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

class Solution {

    public static int mismatch(String a, String b, int ii, int jj, int xx) {
        int i, j = 0;
        for (i = 0; i < xx; i++) {
            if (a.charAt(ii) != b.charAt(jj)) {
                j++;
            }
            ii++;
            jj++;
        }
        return j;
    }

    public static boolean find(int x, String a, String b, int kx) {
        int nn = a.length();
        for (int i = 0; i <= (nn - x); i++) {
            for (int j = 0; j <= (nn - x); j++) {
                int k;
                k = mismatch(a, b, i, j, x);
                if (k == kx) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String args[]) throws IOException {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t > 0) {
            int k, n;
            String a, b;
            k = scanner.nextInt();
            a = scanner.next();
            b = scanner.next();
            n = a.length();
            int i = (n + k) / 2;
            int st = k, en = n
                while (i != k || i != n) {
                boolean ch = false, chh = false;
                ch = find(i, a, b, k);
                if (i != n) {
                    chh = find(i + 1, a, b, k);
                }
                if (i == n && ch == true) {
                    System.out.println(i);
                    break;
                }
                if (ch == true && chh == false) {
                    System.out.println(i);
                    break;
                }
                if (ch) {
                    st = i;
                    i = (i + en + 1) / 2;
                } else {
                    en = i;
                    i = (st + i) / 2;
                }
            }
            t--;
        }
    }
}

上面的实现正在5.1秒，输入0F 1500串length.But最大时间限制在java中是5sec.if任何一个能改善这种code，请您分享侑thougths

the above implementation is taking 5.1 sec for input 0f 1500 string length.But maximum time limit in java is 5sec.if any one can improve this code,please kindly share yor thougths

推荐答案

您code在网站上不采取5.1s。他们停止，一旦超过时限运行您code。您的code可能再碰分钟。所以，即使你使用这种算法优化它，你将再次得到细节部分5.1s。因此，完成你的算法中，没有优化！

Your code doesn't take 5.1s on the site. They stop running your code as soon as it exceeds the time limit. Your code might be taking even minutes. So, even if you optimize it with this algorithm you will again get 5.1s in details section. So work on your algo, not optimization!

这篇关于两个字符串之间串差的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！