Post
Ask Question

Get Common SubString From Two Strings

I came from science, I have never had a chance to learn or play a game such as an algorithm in my student career, although I like logic thinking, I like the algorithm game, but I missed the age period to play this kind of game. Most algorithm problems I met are in interviews. In my view, these kinds of tricks are just boby level games, but if you did not have related training previously, you might not get the solution immediately. So, I will open a topic, or series, to record the algorithm questions I met or I played previously. The first one will be this. Please do not laugh at me to play this pupil question, you can think those also meant BASIC.

This series will include,

I will add more on this topic probably from my notes or practice code.

Introduction

This is the structure of this article,

  • Introduction
  • A - Get Common SubString from two Strings
    • Solution one: Two One Dimension Embedded Loops
    • Solution Two: Two One Dimension Parallel Loops
  • B - Get  Length of the Longest Substring Shared by Two Strings
  • C - Get the Longest Substring Shared by Two Strings

A - Get Common SubString from two Strings
 

Question

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

Solution one: Two One Dimension Embedded Loops

The main program,

class GetSameString {
    public static void Main(string[] args) {
        string s1 = "This is a test";
        string s2 = "test";
        //string s2 = "no";
        string result = Result.twoStrings(s1, s2);
        Console.WriteLine(result);
        Console.ReadLine();
    }
}

In the code, you may change the input as you like, for example, you may comment out string "test", using the string "no", and so on.

The straightforward solution is to make two one dimension loops, one is embedded to another,

public static string twoStrings1(string s1, string s2) {
    for (int i = 0; i < s1.Length; i++)
        for (int j = 0; j < s2.Length; j++)
            if (s1[i] == s2[j]) return "YES";
    return "NO";
}

This solution is easy to get, but it is not efficient. It will be calculate s1.length * s2.length times.

Solution Two: Two One Dimension Parallel Loops

public static string twoStrings0(string s1, string s2) {
    bool[] v = new bool[126];
    v = (v.Select(x => x = false)).ToArray(); // could be ignore because bool default value is false
    for (int i = 0; i < s1.Length; i++) v[s1[i]] = true;
    for (int i = 0; i < s2.Length; i++)
        if (v[s2[i]]) return "YES";
    return "NO";
}

This will be efficient, calculate s1.length + s2.length time.

Note
The Char could be in an integer type, for example, using the debugger, you can see that,

So, in our context,

s1[i] will be an integer, represents the Char. For how to get ASCII value for a char, see Get String ASCII Value in C#.

B - Get  Length of the Longest Substring Shared by Two Strings

Solution

public static int twoStrings(string s1, string s2) {
    // We need two demention array:
    int[, ] matrix = new int[s1.Length + 1, s2.Length + 1];
    int longest = 0, I = 0, J = 0;
    //Get longth for the longest common string
    for (int i = 0; i <= s1.Length; i++) {
        for (int j = 0; j <= s2.Length; j++) {
            if (i == 0 || j == 0) matrix[i, j] = 0;
            else if (s1[i - 1] == s2[j - 1]) {
                matrix[i, j] = matrix[i - 1, j - 1] + 1;
                if (longest < matrix[i, j]) {
                    longest = matrix[i, j];
                    I = i;
                    J = j;
                }
            } else matrix[i, j] = 0;
        }
    }
    return longest;
}

For this solution, we need and have to use two dimension loops.

C - Get the Longest Substring Shared by Two Strings

Solution

public static string twoStrings(string s1, string s2) {
    // We need two demention array:
    int[, ] matrix = new int[s1.Length + 1, s2.Length + 1];
    int longest = 0, I = 0, J = 0;
    //Get longth for the longest common string
    for (int i = 0; i <= s1.Length; i++) {
        for (int j = 0; j <= s2.Length; j++) {
            if (i == 0 || j == 0) matrix[i, j] = 0;
            else if (s1[i - 1] == s2[j - 1]) {
                matrix[i, j] = matrix[i - 1, j - 1] + 1;
                if (longest < matrix[i, j]) {
                    longest = matrix[i, j];
                    I = i;
                    J = j;
                }
            } else matrix[i, j] = 0;
        }
    }
    String resultStr = "";
    while (matrix[I, J] != 0) {
        resultStr = s1[I - 1] + resultStr; // or Y[col-1]
        --longest;
        // move diagonally up to previous cell
        I--;
        J--;
    }
    // required longest common substring, could be nothing
    return (resultStr);
}

Reference


Similar Articles