Algorithm/Substring Diff at master · TechRaY/Algorithm · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//https://www.hackerrank.com/challenges/substring-diff/problem

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;


public class Solution {

    static int c[][];
    static int l,s;

    static boolean solve(int mid)
    {
	   for(int i = mid;i <= l;i++)
        {
                for(int j = mid;j <= l;j++)
                {
                    int tmp = c[i][j] - c[i-mid][j-mid];
                    if(tmp <= s) return true;
                }
         }
        return false;
    }

    public static void main(String args[] ) throws Exception {

        Scanner sc=new Scanner(System.in);
        int t;
        t=sc.nextInt();

	while(t-->0)
	{
		s=sc.nextInt();
		char a[],b[];
        String la=sc.nextLine();
        System.out.println(la);

        String k[]=la.split(" ");

       // System.out.println(k[0]+" "+k[1]+" "+k[2]);

        a=k[1].toCharArray();
        b=k[2].toCharArray();

		l = a.length;
        c=new int[l+1][l+1];

		for(int i=0;i<l;++i)
		{
		  for(int j=0;j<l;++j)
		  {
		  	  	if(a[i]==b[j])
		  	  	 c[i+1][j+1] = c[i][j] ;
		  	  	 else
		  	  	 c[i+1][j+1] = c[i][j] +1;
		  }

              System.out.println(Arrays.toString(c[i]));

		  }
		  int low = 0,high = l,mid;
            while(low < high)
			{
                mid = (low + high + 1) >> 1;
                if(solve(mid)) low = mid;
                else high = mid - 1;
            }
		  System.out.println(low);
	}

    }
}