Databases
StackOverflow2013
Postsdbo
POsubstring difference between two strings
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POsubstring difference between two strings
    primarykey
    data
    text
    <p>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 <code>{ 0&lt;=x&lt;k | pi+x not equal to qj+x| }</code>.</p> <p>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 <code>M(i, j, L) &lt;= K</code>. Of course, we should also have <code>i+L-1 &lt;=n</code> and <code>j+L-1 &lt;=n</code>. Input</p> <p>First line of input contains a single integer T (1 &lt;=T &lt;=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</p> <p>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) &lt;=K.</p> <p>Constraints</p> <p>0 &lt;= K &lt;= length of the string P Both P &amp; Q would have the same length The size of each of the string would be at the max 1500 All characters in P &amp; Q are lower-case English letters.</p> <p>Sample Input</p> <pre><code>3 2 tabriz torino 0 abacba abcaba 3 helloworld yellomarin </code></pre> <p>Sample Output</p> <pre><code>4 3 8 </code></pre> <p>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.</p> <p>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.</p> <p>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.</p> <p>here is my implementation</p> <pre><code>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 &lt; 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 &lt;= (nn - x); i++) { for (int j = 0; j &lt;= (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 &gt; 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 &amp;&amp; ch == true) { System.out.println(i); break; } if (ch == true &amp;&amp; chh == false) { System.out.println(i); break; } if (ch) { st = i; i = (i + en + 1) / 2; } else { en = i; i = (st + i) / 2; } } t--; } } } </code></pre> <p>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</p>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USGangnus
    1. USSiva Krishna Aleti
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POsubstring difference between two strings
      1. This table or related slice is empty.
      1. VTDownMod
    2. VO
      singulars
      1. POsubstring difference between two strings
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POsubstring difference between two strings
      1. This table or related slice is empty.
      1. VTApproveEditSuggestion
    1. COThis looks like a homework or programming contest problem. I'm adding the homework tag. If it doesn't apply, feel free to remove it.
      singulars
      1. POsubstring difference between two strings
      1. USAdam Mihalcin
    2. COactually i solved that problem but it is taking more time
      singulars
      1. POsubstring difference between two strings
      1. USSiva Krishna Aleti
    3. COjust i have to reduce 0.1 sec
      singulars
      1. POsubstring difference between two strings
      1. USSiva Krishna Aleti
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload