Java – how to compare two strings to find common substring

javastring

i get termination due to timeout error when i compile. Please help me

Given two strings, determine if they share a common substring. A substring may be as small as one character.

For example, the words "a", "and", "art" share the common substring "a" . The words "be" and "cat" do not share a substring.

Input Format

The first line contains a single integer , the number of test cases.

The following pairs of lines are as follows:

The first line contains string s1 .
The second line contains string s2 .

Output Format

For each pair of strings, return YES or NO.

my code in java

public static void main(String args[])
{
    String s1,s2;
    int n;
    Scanner s= new Scanner(System.in);
    n=s.nextInt();
    while(n>0)
    {    
    int flag = 0;
        s1=s.next();

    s2=s.next();
    for(int i=0;i<s1.length();i++)
    {
        for(int j=i;j<s2.length();j++)
        {
            if(s1.charAt(i)==s2.charAt(j))
            {
                flag=1;
            }
        }
    }


        if(flag==1)
        {
            System.out.println("YES");
        }
        else
        {
            System.out.println("NO");
        }
        n--;
}
}

}

any tips?

Best Answer

The reason for the timeout is probably: to compare two strings that each are 1.000.000 characters long, your code needs 1.000.000 * 1.000.000 comparisons, always.

There is a faster algorithm that only needs 2 * 1.000.000 comparisons. You should use the faster algorithm instead. Its basic idea is:

  • for each character in s1: add the character to a set (this is the first million)
  • for each character in s2: test whether the set from step 1 contains the character, and if so, return "yes" immediately (this is the second million)

Java already provides a BitSet data type that does all you need. It is used like this:

BitSet seenInS1 = new BitSet();
seenInS1.set('x');
seenInS1.get('x');
Related Topic